我在JavaScript中遇到了一个问题，无法编写代码从n个包含m个元素的数组中生成组合。我看到过类似于其他语言的这种问题，但答案涉及我不知道如何翻译的语法或库魔法。
考虑以下数据：
[[0,1], [0,1,2,3], [0,1,2]]
有三个数组，它们中的元素数量不同。我的目标是通过组合每个数组中的一个元素来获取所有组合。
例如：
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]]
任何帮助将不胜感激。
以下是一个非常简单和短小的示例，使用递归辅助函数：
function cartesian(...args) {
var r = [], max = args.length-1;
function helper(arr, i) {
for (var j=0, l=args[i].length; j<l; j++) {
var a = arr.slice(0); // clone arr
a.push(args[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(args)，而不是使用剩余参数语法。
// JS
function* cartesianIterator(head, ...tail) {
const remainder = tail.length ? cartesianIterator(...tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}
// get values:
const cartesian = items => [...cartesianIterator(items)];
console.log(cartesian(input));
// TS
function* cartesianIterator<T>(items: T[][]): Generator<T[]> {
const remainder = items.length > 1 ? cartesianIterator(items.slice(1)) : [[]];
for (let r of remainder) for (let h of items.at(0)!) yield [h, ...r];
}
// get values:
const cartesian = <T>(items: T[][]) => [...cartesianIterator(items)];
console.log(cartesian(input));
你可以采用迭代的方式构建子数组。
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; }[[0, 1], [0, 1, 2, 3], [[0], [1], [2]]] 时呢？ - Reduconst charSet = [["A", "B"],["C", "D", "E"],["F", "G", "H", "I"]];
console.log(charSet.reduce((a,b)=>a.flatMap(x=>b.map(y=>x+y)),['']))经过一些研究，我发现了一个相关的先前问题：找到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/上放置了一个可工作的副本，它接受你之前提供的数组（[[0,1], [0,1,2,3], [0,1,2]]），并将结果输出到浏览器控制台。
仅供娱乐，这是我第一个答案中解决方案的更多功能变体：
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;
}
为了达到最佳速度，我们可以动态编��自己的循环：
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);
}
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))这段代码仍然可以使用三元运算符缩短，但为了可读性，我更喜欢第一个版本。
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))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;
};
// 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]]));
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]])));
cartesian([ [ 1, 2 ], [ "a", "b" ] ])与cartesian([ 1, 2 ], [ "a", "b" ])，但函数签名显然需要分别为cartesian(arrays)和cartesian(...arrays)。 - Sebastian Simon