4

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.

Improve this question
2
  • 3
    geeksforgeeks.org/… hope this solves your problem. Commented Nov 17, 2016 at 12:30
  • Here is a small and simple solution based on recursion: (combo = arr => { if (!arr.length) return []; if (arr.length === 1) return [arr]; const results = []; for (let index = arr.length; index--;) { const rest = arr.slice(); rest.splice(index, 1); combo(rest).forEach(combination => { results.push([arr[index]].concat(combination)) }); } return results; })([0, 1, 2]) Commented Apr 5, 2020 at 17:32

2 Answers 2

Reset to default
11

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; }

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I'm curious about 'array.length || result.push(temp);' Can you explain me how it works? Thanks :)
@LimeInTheCoconut, i change the answer to a more declarative style. and yes, the expession is always true, but it should test if array is empty, so temp should be pushed to the result set.
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');

Improve this answer

2 Comments

please have a look to my result, regarding performance, i get something below 8 ms and yours need around 360 ms.
@NinaScholz Nice update, my performance test was on your original.. I think I want to marry you :), I'm all for you getting the accepted answer btw.. How come you wasn't put up for voting for Moderator election. You would get my vote. Smart without the attitude..

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.