JavaScript - 从具有m个元素的n个数组生成组合

Question

我在编写代码时难以在JavaScript中生成包含m个元素的n个数组的组合.我已经在其他语言中看到了类似的问题,但答案包含语法或库魔法,我不确定如何翻译.

考虑这些数据:

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

3个数组,其中包含不同数量的元素.我想要做的是通过组合每个数组中的项来获得所有组合.

例如:

0,0,0 // item 0 from array 0, item 0 from array 1, item 0 from array 2
0,0,1
0,0,2
0,1,0
0,1,1
0,1,2
0,2,0
0,2,1
0,2,2

等等.

如果数组的数量是固定的,那么很容易进行硬编码实现.但阵列的数量可能会有所不同:

[[0,1], [0,1]]
[[0,1,3,4], [0,1], [0], [0,1]]

任何帮助将非常感激.

Answer 1

这是一个非常简单和短的使用递归辅助函数:

function cartesian() {
    var r = [], arg = arguments, max = arg.length-1;
    function helper(arr, i) {
        for (var j=0, l=arg[i].length; j<l; j++) {
            var a = arr.slice(0); // clone arr
            a.push(arg[i][j]);
            if (i==max)
                r.push(a);
            else
                helper(a, i+1);
        }
    }
    helper([], 0);
    return r;
}

用法:

cartesian([0,1], [0,1,2,3], [0,1,2]);

为了使功能拍摄数组的数组,只是改变了签名function cartesian(arg),这样arg一个参数,而不是全部arguments.

Answer 2

您可以通过构建子数组来采用迭代方法.

var parts = [[0, 1], [0, 1, 2, 3], [0, 1, 2]],
    result = parts.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));

console.log(result.map(a => a.join(', ')));

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

Answer 3

const charSet = [["A", "B"],["C", "D", "E"],["F", "G", "H", "I"]];
console.log(charSet.reduce((a,b)=>a.flatMap(x=>b.map(y=>x+y)),['']))

Answer 4

我建议一个简单的递归生成器函数:

// Generate all combinations of array elements:
function* cartesian(head, ...tail) {
  let remainder = tail.length ? cartesian(...tail) : [[]];
  for (let r of remainder) for (let h of head) yield [h, ...r];
}


// Example:
for (let c of cartesian([0,1], [0,1,2,3], [0,1,2])) {
  console.log(...c);
}

Answer 5

在做了一些研究之后，我发现了一个以前的相关问题： Finding All Combinations of JavaScript array values

我从那里改编了一些代码，以便它返回一个包含所有排列的数组数组：

function(arraysToCombine) {
    var divisors = [];
    for (var i = arraysToCombine.length - 1; i >= 0; i--) {
       divisors[i] = divisors[i + 1] ? divisors[i + 1] * arraysToCombine[i + 1].length : 1;
    }

    function getPermutation(n, arraysToCombine) {
       var result = [], 
           curArray;    
       for (var i = 0; i < arraysToCombine.length; i++) {
          curArray = arraysToCombine[i];
          result.push(curArray[Math.floor(n / divisors[i]) % curArray.length]);
       }    
       return result;
    }

    var numPerms = arraysToCombine[0].length;
    for(var i = 1; i < arraysToCombine.length; i++) {
        numPerms *= arraysToCombine[i].length;
    }

    var combinations = [];
    for(var i = 0; i < numPerms; i++) {
        combinations.push(getPermutation(i, arraysToCombine));
    }
    return combinations;
}

我在http://jsfiddle.net/7EakX/上放了一份工作副本，它采用您之前提供的数组 ([[0,1], [0,1,2,3], [0,1,2] ]) 并将结果输出到浏览器控制台。