JavaScript - 考虑订单，生成数组的所有组合 [英] JavaScript - Generating all combinations of an array, considering the order

问题描述

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

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 combinations for each array, but consider the element order. 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]

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.

到目前为止我找到的所有解决方案都只创建了与顺序无关的数组，因此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的解决方案看起来很不错，但它确实有点阵列concat&切片，所以这对于较大的集合可能更好，因为它避免了这种情况。我确实使用一个对象来进行重复检查，但是在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.

只是好奇，性能测试也是如此。
做[1,2,3,4,5,6,7]，使用@Nina的解决方案需要38.8秒。
我的做法是175毫米..所以数组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屋！