JavaScript - 使用m个元素生成n个数组的组合

I'm having trouble coming up with code to generate combinations from n number of arrays with m number of elements in them, in JavaScript. I've seen similar questions about this for other languages, but the answers incorporate syntactic or library magic that I'm unsure how to translate.

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

Consider this data:

考虑这些数据：

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

3 arrays, with a different number of elements in them. What I want to do is get all combinations by combining an item from each array.

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

For example:

例如：

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

And so on.

等等。

If the number of arrays were fixed, it would be easy to make a hard coded implementation. But the number of arrays may vary:

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

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

Any help would be much appreciated.

任何帮助将非常感激。

8 个解决方案

#1

Here is a quite simple and short one using a recursive helper function:

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

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

Usage:

用法：

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

To make the function take an array of arrays, just change the signature to function cartesian(arg) so that arg is a parameter instead of all arguments.

要使函数采用数组数组，只需将签名更改为函数cartesian（arg），以便arg是一个参数而不是所有参数。

#2

I suggest a simple recursive generator function:

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

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

#3

You could take an iterative approach by building sub arrays.

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

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

#4

After doing a little research I discovered a previous related question: Finding All Combinations of JavaScript array values

在做了一些研究后，我发现了一个先前的相关问题：查找JavaScript数组值的所有组合

I've adapted some of the code from there so that it returns an array of arrays containing all of the permutations:

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

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

I've put a working copy at http://jsfiddle.net/7EakX/ that takes the array you gave earlier ([[0,1], [0,1,2,3], [0,1,2]]) and outputs the result to the browser console.

我在http://jsfiddle.net/7EakX/上放了一个工作副本，它带有你之前给出的数组（[[0,1]，[0,1,2,3]，[0,1,2] ]）并将结果输出到浏览器控制台。

#5

Just for fun, here's a more functional variant of the solution in my first answer:

只是为了好玩，这是我的第一个答案中解决方案的更多功能变体：

function cartesian() {
    var r = [], args = Array.from(arguments);
    args.reduceRight(function(cont, factor, i) {
        return function(arr) {
            for (var j=0, l=factor.length; j<l; j++) {
                var a = arr.slice(); // clone arr
                a[i] = factor[j];
                cont(a);
            }
        };
    }, Array.prototype.push.bind(r))(new Array(args.length));
    return r;
}

Alternative, for full speed we can dynamically compile our own loops:

另外，为了全速，我们可以动态编译自己的循环：

function cartesian() {
    return (cartesian.cache[arguments.length] || cartesian.compile(arguments.length)).apply(null, arguments);
}
cartesian.cache = [];
cartesian.compile = function compile(n) {
    var args = [],
        indent = "",
        up = "",
        down = "";
    for (var i=0; i<n; i++) {
        var arr = "$"+String.fromCharCode(97+i),
            ind = String.fromCharCode(105+i);
        args.push(arr);
        up += indent+"for (var "+ind+"=0, l"+arr+"="+arr+".length; "+ind+"<l"+arr+"; "+ind+"++) {\n";
        down = indent+"}\n"+down;
        indent += "  ";
        up += indent+"arr["+i+"] = "+arr+"["+ind+"];\n";
    }
    var body = "var res=[],\n    arr=[];\n"+up+indent+"res.push(arr.slice());\n"+down+"return res;";
    return cartesian.cache[n] = new Function(args, body);
}

#6

var f = function(arr){
    if(typeof arr !== 'object'){
        return false;
    }

    arr = arr.filter(function(elem){ return (elem !== null); }); // remove empty elements - make sure length is correct
    var len = arr.length;

    var nextPerm = function(){ // increase the counter(s)
        var i = 0;

        while(i < len)
        {
            arr[i].counter++;

            if(arr[i].counter >= arr[i].length){
                arr[i].counter = 0;
                i++;
            }else{
                return false;
            }
        }

        return true;
    };

    var getPerm = function(){ // get the current permutation
        var perm_arr = [];

        for(var i = 0; i < len; i++)
        {
            perm_arr.push(arr[i][arr[i].counter]);
        }

        return perm_arr;
    };

    var new_arr = [];

    for(var i = 0; i < len; i++) // set up a counter property inside the arrays
    {
        arr[i].counter = 0;
    }

    while(true)
    {
        new_arr.push(getPerm()); // add current permutation to the new array

        if(nextPerm() === true){ // get next permutation, if returns true, we got them all
            break;
        }
    }

    return new_arr;
};

#7

Here's another way of doing it. I treat the indices of all of the arrays like a number whose digits are all different bases (like time and dates), using the length of the array as the radix.

这是另一种方法。我将所有数组的索引视为一个数字，其数字都是不同的数字（如时间和日期），使用数组的长度作为基数。

So, using your first set of data, the first digit is base 2, the second is base 4, and the third is base 3. The counter starts 000, then goes 001, 002, then 010. The digits correspond to indices in the arrays, and since order is preserved, this is no problem.

因此，使用您的第一组数据，第一个数字是基数2，第二个数字是基数4，第三个数字是基数3.计数器开始000，然后是001,002，然后是010.数字对应于数组，并且由于保留了顺序，这没有问题。

I have a fiddle with it working here: http://jsfiddle.net/Rykus0/DS9Ea/1/

我在这里工作的小提琴：http：//jsfiddle.net/Rykus0/DS9Ea/1/

and here is the code:

这是代码：

// Arbitrary base x number class 
var BaseX = function(initRadix){
    this.radix     = initRadix ? initRadix : 1;    
    this.value     = 0;
    this.increment = function(){
        return( (this.value = (this.value + 1) % this.radix) === 0);
    }
}

function combinations(input){
    var output    = [],    // Array containing the resulting combinations
        counters  = [],    // Array of counters corresponding to our input arrays
        remainder = false, // Did adding one cause the previous digit to rollover?
        temp;              // Holds one combination to be pushed into the output array

    // Initialize the counters
    for( var i = input.length-1; i >= 0; i-- ){
        counters.unshift(new BaseX(input[i].length));
    }

    // Get all possible combinations
    // Loop through until the first counter rolls over
    while( !remainder ){
        temp      = [];   // Reset the temporary value collection array
        remainder = true; // Always increment the last array counter

        // Process each of the arrays
        for( i = input.length-1; i >= 0; i-- ){
            temp.unshift(input[i][counters[i].value]); // Add this array's value to the result

            // If the counter to the right rolled over, increment this one.
            if( remainder ){
                remainder = counters[i].increment();
            }
        }
        output.push(temp); // Collect the results.
    }

    return output;
}

// Input is an array of arrays
console.log(combinations([[0,1], [0,1,2,3], [0,1,2]]));

#8

Another implementation with ES6 recursive style

另一种采用ES6递归样式的实现

Array.prototype.cartesian = function(a,...as){
  return a ? this.reduce((p,c) => (p.push(...a.cartesian(...as).map(e => as.length ? [c,...e] : [c,e])),p),[])
           : this;
};

console.log(JSON.stringify([0,1].cartesian([0,1,2,3], [[0],[1],[2]])));