JavaScript – 从m个元素生成n个数组的组合
我遇到了麻烦，想用代码来生成n个数组中有m个元素的组合，在JavaScript中。 我已经看到了类似的其他语言的问题，但答案包括我不确定如何翻译句法或库的魔法。
考虑这些数据：
[[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
等等。
如果数组的数量是固定的，那么很容易做出硬编码的实现。 但是arrays的数量可能会有所不同：
[[0,1], [0,1]] [[0,1,3,4], [0,1], [0], [0,1]]
任何帮助将不胜感激。
这是一个非常简单和短的使用recursion辅助函数：
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 。
在做了一点研究后，我发现了一个以前的相关问题： 查找JavaScript数组值的所有组合
我已经调整了一些代码，以便返回一个包含所有排列的数组数组：
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/上写了一个工作副本，它将你之前给出的数组（%5B%5B0,1%5D，%5B0,1,2,3%5D，%5B0,1,2%5D ]）并将结果输出到浏览器控制台。
只是为了好玩，下面是第一个答案中解决scheme的更多function变体：
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; }
另外，为了全速，我们可以dynamic地编译我们自己的循环：
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); }
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; };
这是另一种方法。 我将所有数组的索引视为一个数字，它们的数字都是不同的基数（如时间和date），使用数组的长度作为基数。
所以，使用你的第一组数据，第一个数字是基数2，第二个数字是基数4，第三个是基数3.计数器开始000，然后是001，002，然后是010.这些数字对应于数组，因为顺序被保留，这是没有问题的。
我有一个小提琴在这里工作： http : //jsfiddle.net/Rykus0/DS9Ea/1/
这里是代码：
// 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]]));
我build议一个简单的recursion生成器函数 ：
// 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); }
用ES6recursion样式的另一个实现
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]])));
