javascript - Shuffle an array as many as possible

Question

I have an array like this

[0,2,3]

The possible shuffling of this array are

[0,2,3], [2,3,0], [3,0,2], [3,2,0], [0,3,2], [2,0,3]

How can I get these combinations? The only idea I have in mind currently is

n = maximum num of possible combinations, coms = []
while( coms.length <= n )
    temp = shuffle( original the array );
    if temp is there in coms
       return
    else 
       coms.push(temp);

But I do not think this is efficient, as here we are blindly depending on uniform distribution of shuffle method.

Is there alternative findings for this problem?

Answer 1

The first thing to note is that the number of permutations increases very fast with regard to the number of elements (13 elements = 6 bilion permutations), so any kind of algorithm that generates them will deteriorate in performance for a large enough input array.

The second thing to note is that since the number of permutations is very large, storing them in memory is expensive, so you're way better off using a generator for your permutations and doing stuff with them as they are generated.

The third thing to note is that recursive algorithms bring a large overhead, so even if you find a recursive solution, you should strive to get a non-recursive one. Obtaining a non-recursive solution if a recursive one exists is always possible, but it may increase the complexity of the code.

I have written a non recursive implementation for you, based on the Steinhaus–Johnson–Trotter algorithm (http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm)

function swap(arr, a,b){
  var temp = arr[a];
  arr[a]=arr[b];
  arr[b]=temp;
}

function factorial(n) {
  var val = 1;
  for (var i=1; i<n; i++) {
    val *= i;
  }
  return val;
}


function permute(perm, func){
  var total = factorial(perm.length);

  for (var j=0, i=0, inc=1;  j<total;  j++, inc*=-1, i+=inc) {

    for (; i<perm.length-1 && i>=0; i+=inc) {
      func.call(perm);
      swap (perm, i, i+1);
    }  

    func.call(perm);

    if (inc === 1) {
      swap(perm, 0,1);
    } else {
      swap(perm, perm.length-1, perm.length-2);
    }
  }
}

console.clear();

count = 0;
permute([1,2,3,4,5,6], function(){console.log(this); count++;});

console.log('There have been ' + count + ' permutations');

http://jsbin.com/eXefawe/2/edit