查找 JavaScript 数组值的所有组合(笛卡儿积)

我怎样才能产生 N 个可变长度的 JavaScript 数组中所有值的组合？

假设我有 N 个 JavaScript 数组，例如。

var first = ['a', 'b', 'c', 'd'];
var second = ['e'];
var third =  ['f', 'g', 'h', 'i', 'j'];

(在这个例子中有三个数组，但是它有 N 个数组来解决这个问题。)

我想输出它们所有值的组合

aef
aeg
aeh
aei
aej
bef
beg
....
dej

编辑: 这是我的工作版本，使用朋友的接受的答案作为基础。

var allArrays = [['a', 'b'], ['c', 'z'], ['d', 'e', 'f']];


function allPossibleCases(arr) {
if (arr.length === 0) {
return [];
}
else if (arr.length ===1){
return arr[0];
}
else {
var result = [];
var allCasesOfRest = allPossibleCases(arr.slice(1));  // recur with the rest of array
for (var c in allCasesOfRest) {
for (var i = 0; i < arr[0].length; i++) {
result.push(arr[0][i] + allCasesOfRest[c]);
}
}
return result;
}


}
var results = allPossibleCases(allArrays);
//outputs ["acd", "bcd", "azd", "bzd", "ace", "bce", "aze", "bze", "acf", "bcf", "azf", "bzf"]
73565 次浏览
小开
最佳答案

这不是排列，参见维基百科的 排列定义。

但是你可以通过 递归实现这一点:

var allArrays = [
['a', 'b'],
['c'],
['d', 'e', 'f']
]


function allPossibleCases(arr) {
if (arr.length == 1) {
return arr[0];
} else {
var result = [];
var allCasesOfRest = allPossibleCases(arr.slice(1)); // recur with the rest of array
for (var i = 0; i < allCasesOfRest.length; i++) {
for (var j = 0; j < arr[0].length; j++) {
result.push(arr[0][j] + allCasesOfRest[i]);
}
}
return result;
}


}


console.log(allPossibleCases(allArrays))

您也可以使用循环来实现它，但是这将有点棘手，并且需要实现您自己的类似堆栈。

小开

您不需要递归，也不需要大量嵌套循环，甚至不需要在内存中生成/存储整个排列数组。

由于排列次数是每个数组长度的乘积(称为 numPerms) ，所以可以创建一个函数 getPermutation(n)，通过基于 n计算它需要从中检索字符的索引，返回索引 0和 numPerms - 1之间的唯一排列。

这是怎么做到的？如果你想在数组上创建排列，每个排列包含: [0,1,2，... 9] ，这很简单... 第245个排列(n = 245)是“245”，相当直观，或者:

arrayHundreds[Math.floor(n / 100) % 10]
+ arrayTens[Math.floor(n / 10) % 10]
+ arrayOnes[Math.floor(n / 1) % 10]

问题的复杂性在于数组大小不同。我们可以通过替换 n/100、 n/10等来解决这个问题。.和其他的除数。为此，我们可以很容易地预先计算一个约数数组。在上面的例子中，100的除数等于 arrayTens.length * arrayOnes.length。因此，我们可以计算给定数组的除数是剩余数组长度的乘积。最后一个数组的除数总是为1。而且，我们不是通过10进行修改，而是通过当前数组的长度进行修改。

示例代码如下:

var allArrays = [first, second, third, ...];


// Pre-calculate divisors
var divisors = [];
for (var i = allArrays.length - 1; i >= 0; i--) {
divisors[i] = divisors[i + 1] ? divisors[i + 1] * allArrays[i + 1].length : 1;
}


function getPermutation(n) {
var result = "", curArray;


for (var i = 0; i < allArrays.length; i++) {
curArray = allArrays[i];
result += curArray[Math.floor(n / divisors[i]) % curArray.length];
}


return result;
}
小开

提供答案对我来说太难了，所以我的解决办法是:

var allArrays = new Array(['a', 'b'], ['c', 'z'], ['d', 'e', 'f']);


function getPermutation(array, prefix) {
prefix = prefix || '';
if (!array.length) {
return prefix;
}


var result = array[0].reduce(function(result, value) {
return result.concat(getPermutation(array.slice(1), prefix + value));
}, []);
return result;
}


console.log(getPermutation(allArrays));

小开

你可以使用一个典型的回溯:

function cartesianProductConcatenate(arr) {
var data = new Array(arr.length);
return (function* recursive(pos) {
if(pos === arr.length) yield data.join('');
else for(var i=0; i<arr[pos].length; ++i) {
data[pos] = arr[pos][i];
yield* recursive(pos+1);
}
})(0);
}

我使用了生成器函数来避免同时分配所有结果，但是如果您愿意，可以这样做

[...cartesianProductConcatenate([['a', 'b'], ['c', 'z'], ['d', 'e', 'f']])];
// ["acd","ace","acf","azd","aze","azf","bcd","bce","bcf","bzd","bze","bzf"]
小开

我建议一个简单的递归 发电机功能发电机功能如下:

// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
let remainder = tail.length ? cartesian(...tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}


// Example:
const first  = ['a', 'b', 'c', 'd'];
const second = ['e'];
const third  = ['f', 'g', 'h', 'i', 'j'];


console.log(...cartesian(first, second, third));

小开

复制 le _ m 的答案直接获取 Array of Array:

function *combinations(arrOfArr) {
let [head, ...tail] = arrOfArr
let remainder = tail.length ? combinations(tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}

希望能节省某人的时间。

小开

下面是根据上面两个答案改编的一个版本，它按照 OP 中指定的顺序生成结果，并返回字符串而不是数组:

function *cartesianProduct(...arrays) {
if (!arrays.length) yield [];
else {
const [tail, ...head] = arrays.reverse();
const beginning = cartesianProduct(...head.reverse());
for (let b of beginning) for (let t of tail) yield b + t;
}
}


const first = ['a', 'b', 'c', 'd'];
const second = ['e'];
const third =  ['f', 'g', 'h', 'i', 'j'];
console.log([...cartesianProduct(first, second, third)])
小开

如果您正在寻找一个流兼容的函数，它可以处理任何项类型的二维数组，您可以使用下面的函数。

const getUniqueCombinations = <T>(items : Array<Array<T>>, prepend : Array<T> = []) : Array<Array<T>> => {
if(!items || items.length === 0) return [prepend];


let out = [];


for(let i = 0; i < items[0].length; i++){
out = [...out, ...getUniqueCombinations(items.slice(1), [...prepend, items[0][i]])];
}


return out;
}

操作的可视化:

在:

[
[Obj1, Obj2, Obj3],
[Obj4, Obj5],
[Obj6, Obj7]
]

出去:

[
[Obj1, Obj4, Obj6 ],
[Obj1, Obj4, Obj7 ],
[Obj1, Obj5, Obj6 ],
[Obj1, Obj5, Obj7 ],
[Obj2, Obj4, Obj6 ],
[Obj2, Obj4, Obj7 ],
[Obj2, Obj5, Obj6 ],
[Obj2, Obj5, Obj7 ],
[Obj3, Obj4, Obj6 ],
[Obj3, Obj4, Obj7 ],
[Obj3, Obj5, Obj6 ],
[Obj3, Obj5, Obj7 ]
]
小开

你也可以使用这个函数: 

const result = (arrayOfArrays) => arrayOfArrays.reduce((t, i) => { let ac = []; for (const ti of t) { for (const ii of i) { ac.push(ti + '/' + ii) } } return ac })


result([['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']])
// which will output [ 'a/e/f', 'a/e/g', 'a/e/h','a/e/i','a/e/j','b/e/f','b/e/g','b/e/h','b/e/i','b/e/j','c/e/f','c/e/g','c/e/h','c/e/i','c/e/j','d/e/f','d/e/g','d/e/h','d/e/i','d/e/j']

当然，您可以删除 ac.push(ti + '/' + ii)中的 + '/'，以消除最终结果中的斜杠。您可以将这些 for (... of ...)替换为 forEach 函数(在 return ac之前加上相应的分号) ，任何您更熟悉的函数都可以。

小开

找到密码的最简单方法

const arr1= [ 'a', 'b', 'c', 'd' ];
const arr2= [ '1', '2', '3' ];
const arr3= [ 'x', 'y', ];


const all = [arr1, arr2, arr3];


const output = all.reduce((acc, cu) => {
let ret = [];
acc.map(obj => {
cu.map(obj_1 => {
ret.push(obj + '-' + obj_1)
});
});
return ret;
})


console.log(output);

小开

你可以通过生成一个笛卡儿积来进行单线操作。

result = items.reduce(
(a, b) => a.reduce(
(r, v) => r.concat(b.map(w => [].concat(v, w))),
[]
)
);


var items = [['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']],
result = items.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; }

小开

没有递归的数组方法:

const combinations = [['1', '2', '3'], ['4', '5', '6'], ['7', '8']];
let outputCombinations = combinations[0]


combinations.slice(1).forEach(row => {
outputCombinations = outputCombinations.reduce((acc, existing) =>
acc.concat(row.map(item => existing + item))
, []);
});


console.log(outputCombinations);
小开

您可以创建一个2D 数组和 reduce它。然后使用 flatMap在累加器数组中创建字符串组合以及迭代并连接它们的当前数组。

const data = [ ['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j'] ]


const output = data.reduce((acc, cur) => acc.flatMap(c => cur.map(n => c + n)) )


console.log(output)

小开

2021年版的邓永锵大作 回答
也受到了 Neil Mountford 的回答的启发

const getAllCombinations = (arraysToCombine) => {
const divisors = [];
let permsCount = 1;
for (let i = arraysToCombine.length - 1; i >= 0; i--) {
divisors[i] = divisors[i + 1] ? divisors[i + 1] * arraysToCombine[i + 1].length : 1;
permsCount *= (arraysToCombine[i].length || 1);
}


const getCombination = (n, arrays, divisors) => arrays.reduce((acc, arr, i) => {
acc.push(arr[Math.floor(n / divisors[i]) % arr.length]);
return acc;
}, []);


const combinations = [];
for (let i = 0; i < permsCount; i++) {
combinations.push(getCombination(i, arraysToCombine, divisors));
}
return combinations;
};


console.log(getAllCombinations([['a', 'b'], ['c', 'z'], ['d', 'e', 'f']]));

基准: https://jsbench.me/gdkmxhm36d/1

小开 
let arr1 = [`a`, `b`, `c`];
let arr2 = [`p`, `q`, `r`];
let arr3 = [`x`, `y`, `z`];
let result = [];


arr1.forEach(e1 => {
arr2.forEach(e2 => {
arr3.forEach(e3 => {
result[result.length] = e1 + e2 + e3;
});
});
});




console.log(result);
/*
output:
[
'apx', 'apy', 'apz', 'aqx',
'aqy', 'aqz', 'arx', 'ary',
'arz', 'bpx', 'bpy', 'bpz',
'bqx', 'bqy', 'bqz', 'brx',
'bry', 'brz', 'cpx', 'cpy',
'cpz', 'cqx', 'cqy', 'cqz',
'crx', 'cry', 'crz'
]
*/
小开

一种不用递归的解决方案，它还包括一个通过 id 检索单个组合的函数:

function getCombination(data, i) {
return data.map(group => {
let choice = group[i % group.length]
i = (i / group.length) | 0;
return choice;
});
}


function* combinations(data) {
let count = data.reduce((sum, {length}) => sum * length, 1);
for (let i = 0; i < count; i++) {
yield getCombination(data, i);
}
}


let data = [['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']];


for (let combination of combinations(data)) {
console.log(...combination);
}


提交答案