JavaScript

Question

我有不同的数组，都有数字，但元素数量不同：

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

我需要获取每个数组的所有排列。输出元素的长度应始终与输入数组相同。

这个结果应该是一个数组的数组，像这样：

对于 ar1:

[2, 5]
[5, 2]

对于 ar2:

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

我不需要笛卡尔积，每个数组应该单独处理。

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

解决方案应该适用于输入数组中的任意数量的元素。我们可以假设输入数组中没有重复值。

Answer 1

您可以对 permutation 使用迭代和递归方法，直到没有更多元素要分发为止。

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

不确定这是否是最好的方法，但它似乎有效。

@Nina 的解决方案看起来不错，但它执行了相当多的数组连接和切片操作，因此这对于较大的集合可能更有效，因为它避免了这种情况。我确实使用一个对象来进行重复检查，但是 hashmaps 在 JS 中非常快。

只是好奇，性能测试也是如此。使用@Nina 的解决方案执行 [1,2,3,4,5,6,7] 需要 38.8 秒。做我的 toke 175ms .. 所以数组 concat / slice 是一个巨大的性能损失，标记的重复将有同样的问题。只是需要注意的事情。

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 - 生成数组的所有排列

JavaScript - Generating all permutations of an array

arrays

permutation