JavaScript - Generating all permutations of an array

Question

I have different arrays, all with numbers, but with different number of elements:

var ar1 = [2, 5];
var ar2 = [1, 2, 3];

I need to get all permutations for each array. The length of the output elements should always be the same as the input array.

This result should be an array of arrays, like this:

for ar1:

[2, 5]
[5, 2]

for ar2:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

I don't want a cartesian product, each array should be processed on its own.

All solutions I found so far are creating only order independent arrays, so the result for ar1 is only one array and not two.

The Solution should work for any number of elements in the input array. We can assume that there are no duplicate values in the input array.

Answer 1

You could use for a permutation an iterative and recursive approach until not more elements are to distribute.

function permutation(array) {
    function p(array, temp) {
        var i, x;
        if (!array.length) {
            result.push(temp);
        }
        for (i = 0; i < array.length; i++) {
            x = array.splice(i, 1)[0];
            p(array, temp.concat(x));
            array.splice(i, 0, x);
        }
    }

    var result = [];
    p(array, []);
    return result;
}

console.log('something bigger [1,2,3,4,5,6,7]');
console.time('t1');
permutation([1, 2, 3, 4, 5, 6, 7]);
console.timeEnd('t1');

console.log(permutation([2, 5]));
console.log(permutation([1, 2, 3]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Not sure if this is the best way, but it seems to work.

@Nina's solution looks good, but it does a fair bit of array concat & slice, so this might work better for larger sets as it avoids that. I do use an object for duplicate checking, but hashmaps are super fast in JS.

Just curious, so did a performance test. Doing [1,2,3,4,5,6,7], using @Nina's solution take's 38.8 seconds,. Doing mine toke 175ms.. So the array concat / slice is a massive performance hit, and the marked duplicate will have the same issue. Just something to be aware off.

var ar1 = [2, 5];
var ar2 = [1, 2, 3];

function combo(c) {
  var r = [],
      len = c.length;
      tmp = [];
  function nodup() {
    var got = {};
    for (var l = 0; l < tmp.length; l++) {
      if (got[tmp[l]]) return false;
      got[tmp[l]] = true;
    }
    return true;
  }
  function iter(col,done) {    
    var l, rr;
    if (col === len) {      
      if (nodup()) {
        rr = [];
        for (l = 0; l < tmp.length; l++) 
          rr.push(c[tmp[l]]);        
        r.push(rr);
      }
    } else {
      for (l = 0; l < len; l ++) {            
        tmp[col] = l;
        iter(col +1);
      }
    }
  }
  iter(0);
  return r;
}

console.log(JSON.stringify(combo(ar1)));
console.log(JSON.stringify(combo(ar2)));
console.log('something bigger [1,2,3,4,5,6,7]');
console.time('t1');
combo([1,2,3,4,5,6,7]);
console.timeEnd('t1');