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

JavaScript - Generating combinations from n arrays with m elements

提问by quano

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 中，我无法编写代码来从 n 个数组和 m 个元素生成组合。我已经看到其他语言的类似问题，但答案包含了我不确定如何翻译的句法或库魔法。

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.

任何帮助将非常感激。

回答by Bergi

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 argis a parameter instead of all arguments.

要使函数采用数组数组，只需将签名更改为 ，function cartesian(arg)以便它arg是一个参数而不是allarguments。

回答by Nina Scholz

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

回答by le_m

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

回答by Neil Mountford

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

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

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] ]) 并将结果输出到浏览器控制台。

回答by Bergi

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

回答by Tom Pietrosanti

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

回答by Neob91

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

回答by Redu

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

回答by Code Maniac

You can use a recursive function to get all combinations

您可以使用递归函数来获取所有组合

const charSet = [["A", "B"],["C", "D", "E"],["F", "G", "H", "I"]];

let loopOver = (arr, str = '', final = []) => {
  if (arr.length > 1) {
    arr[0].forEach(v => loopOver(arr.slice(1), str + v, final))
  } else {
    arr[0].forEach(v => final.push(str + v))
  }
  return final
}

console.log(loopOver(charSet))

---

---

This code can still be shorten using ternary but i prefer the first version for readability

这段代码仍然可以使用三元来缩短，但我更喜欢第一个版本的可读性

const charSet = [["A", "B"],["C", "D", "E"],["F", "G", "H", "I"]];

let loopOver = (arr, str = '') => arr[0].map(v => arr.length > 1 ? loopOver(arr.slice(1), str + v) : str + v).flat()

console.log(loopOver(charSet))

回答by u5602117

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)),['']))