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?

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?

• javascript

• check [this][1] and [this][2] post for your answers. [1]: stackoverflow.com/questions/6274339/… [2]: stackoverflow.com/questions/2450954/… – kuldarim Commented Sep 8, 2013 at 6:46
• @Riku Thanks for proving useful links, Here my question is not about shuffle algorithm. I can use Fisher-Yates algorithm. For each iteration I need to check whether I have the same item in the existing array and proceed. It is very time consuming and not performance oriented. – Exception Commented Sep 8, 2013 at 6:48
• 12 "Shuffle" is the wrong keyword; you want "permutation" – Domenic Commented Sep 8, 2013 at 6:52
• 1 possible duplicate of permutations in javascript? – hjpotter92 Commented Sep 8, 2013 at 6:56
• 1 I made a JsPerf with the options posted so far: jsperf.com/permutations-implementation Feel free to test it on more browsers for more accurate results. – Tibos Commented Sep 20, 2013 at 16:38

8 Answers 8

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

Try a recursive approach. Here's a hint: every permutation of [0,2,3] is either

• [0] plus a permutation of [2,3] or
• [2] plus a permutation of [0,3] or
• [3] plus a permutation of [0,2]

As zodiac mentioned the best solution to this problem is a recursive one:

var permute = (function () {
    return permute;

    function permute(list) {
        return list.length ?
            list.reduce(permutate, []) :
            [[]];
    }

    function permutate(permutations, item, index, list) {
        return permutations.concat(permute(
            list.slice(0, index).concat(
            list.slice(index + 1)))
            .map(concat, [item]));
    }

    function concat(list) {
        return this.concat(list);
    }
}());

alert(JSON.stringify(permute([1,2,3])));

Hope that helps.

All permutations of a set can be found by selecting an element in the set and recursively permuting (rearranging) the remaining elements. Backtracking approach can be used for finding the solution.

Algorithm steps (source):

Pseudocode (source):

permute(i) 
   if i == N  output A[N] 
   else 
      for j = i to N do 
         swap(A[i], A[j]) 
         permute(i+1) 
         swap(A[i], A[j])

Javascript implementation (jsFiddle):

Array.prototype.clone = function () {
    return this.slice(0);
};

var input = [1, 2, 3, 4];
var output = [];

function permute(i) {
    if (i == input.length)
        output.push(input.clone());
    else {
        for (var j = i; j < input.length; j++) {
            swap(i, j);
            permute(i + 1);
            swap(i, j); // backtrack
        }
    }
};

function swap(i, j) {
    var temp = input[i];
    input[i] = input[j];
    input[j] = temp;
}

permute(0);
console.log(output);

For an array of length n, we can precompute the number of possible permutations. It's n! (n factorial)

function factorial(n){ return n<=0?1:n*factorial(n-1);}
//There are better ways, but just for illustration's sake

And, we can create a function which maps an integer p between 0...n!-1 to a distinct permutation.

function map(p,orgArr){
 var tempArr=orgArr.slice(); //Create a copy
 var l=orgArr.length;
 var permArr=[];
 var pick; 
 do{
  pick=p%l; //mod operator
  permArr.push(tempArr.splice(pick,1)[0]); //Remove item number pick from the old array and onto the new
  p=(p-pick)/l;
  l--;
 }while(l>=1)
 return permArr;  
}

At this point, all you need to do is create an array ordering=[0,1,2,3,...,factorial(n)-1] and shuffle that. Then, you can loop for(var i=0;i<=ordering.length;i++) doSomething(map(ordering[i],YourArray));

That just leaves the question of how to shuffle the ordering array. I believe that's well documented and outside the scope of your question since the answer depends on your application (i.e. is pseudo random good enough, or do you need some cryptographic strength, speed desired, etc...). See How to randomize (shuffle) a JavaScript array? and many others.

Or, if the number of permutations is so large that you don't want to create this huge ordering array, you just have to distinctly pick values of i for the above loop between 0-n!-1. If just uniformity is needed, rather than randomness, one easy way would be to use primitive roots: http://en.wikipedia.org/wiki/Primitive_root_modulo_n

you don't need to recurse. The demo should make the pattern pretty clear: http://jsfiddle.net/BGYk4/

function shuffle(arr) {
        var output = [];
        var n = arr.length;
        var ways = [];
        for(var i = 0, j = 1; i < n; ways.push(j *= ++i));
        var totalWays = ways.pop();
        for(var i = 0; i < totalWays; i++) {
                var copy = arr.slice();
                output[i] = [];
                for(var k = ways.length - 1; k >= 0; k--) {
                        var c = Math.floor(i/ways[k]) % (k + 2);
                        output[i].push(copy.splice(c,1)[0]);
                }
                output[i].push(copy[0]);
        }
        return output;
}

this should output all possible "shuffles"

console.log(shuffle(['a', 'b', 'c', 'd', 'e']));

this one's cuter (but the output from the other example is much clearer): http://jsfiddle.net/wCnLf/

function shuffle(list) {
    var shufflings = [];
    while(true) {
        var clone = list.slice();
        var shuffling = [];
        var period = 1;
        while(clone.length) {
            var index = Math.floor(shufflings.length / period) % clone.length;
            period *= clone.length;
            shuffling.push(clone.splice(index,1)[0]);
        }
        shufflings.push(shuffling);
        if(shufflings.length == period) return shufflings;
    }
}

and of course it still outputs all possible "shuffles"

console.log(shuffle(['a', 'b', 'c', 'd', 'e']));

tibos example above was exactly what I was looking for but I had some trouble running it, I made another solution as an npm module:

var generator = new Permutation([1, 2, 3]);
while (generator.hasNext()) {
  snippet.log(generator.next());
}

<script src="http://tjcrowder.github.io/simple-snippets-console/snippet.js"></script>
<script src="http://rawgit.com/bcard/iterative-permutation/master/iterative-permutation.js"></script>

https://www.npmjs.com/package/iterative-permutation

https://github.com/bcard/iterative-permutation