JavaScript-生成数组的所有排列 [英] JavaScript - Generating all permutations of an array

问题描述

我有不同的数组，全部带有数字，但元素数量不同:

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:

对于ar1:

[2, 5]
[5, 2]

对于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.

到目前为止，我发现的所有解决方案都仅创建与顺序无关的数组，因此ar1的结果仅是一个数组，而不是两个.

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.

推荐答案

不确定这是否是最好的方法，但似乎可行.

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

@Nina的解决方案看起来不错，但确实做了一些阵列连接&切片，因此这对于较大的集合可能会更好，因为它避免了这种情况.我确实使用了一个对象进行重复检查，但是在JS中哈希表非常快.

@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.

只是好奇，所以进行了性能测试. 使用@Nina的解决方案进行[1,2,3,4,5,6,7]花费38.8秒. 做我的toke 175ms..因此，数组concat/slice严重影响了性能，并且标记的重复项将具有相同的问题.只是需要注意的事情.

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');

这篇关于JavaScript-生成数组的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！