JavaScript 中多个数组的笛卡尔积
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12303989/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Cartesian product of multiple arrays in JavaScript
提问by viebel
How would you implement the Cartesian product of multiple arrays in JavaScript?
你将如何在 JavaScript 中实现多个数组的笛卡尔积？
As an example,
举个例子，
cartesian([1, 2], [10, 20], [100, 200, 300])
should return
应该回来
[
[1, 10, 100],
[1, 10, 200],
[1, 10, 300],
[2, 10, 100],
[2, 10, 200]
...
]
采纳答案by viebel
Here is a functional solution to the problem (without any mutable variable!) using reduceand flatten, provided by underscore.js:
这是使用and的问题的功能解决方案（没有任何可变变量！），由以下提供：reduceflattenunderscore.js
function cartesianProductOf() {
return _.reduce(arguments, function(a, b) {
return _.flatten(_.map(a, function(x) {
return _.map(b, function(y) {
return x.concat([y]);
});
}), true);
}, [ [] ]);
}
// [[1,3,"a"],[1,3,"b"],[1,4,"a"],[1,4,"b"],[2,3,"a"],[2,3,"b"],[2,4,"a"],[2,4,"b"]]
console.log(cartesianProductOf([1, 2], [3, 4], ['a'])); <script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore.js"></script>Remark: This solution was inspired by http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/
备注：此解决方案的灵感来自http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/
回答by rsp
2017 Update: 2-line answer with vanilla JS
2017 年更新：2 线回答与香草 JS
All of the answers here are overly complicated, most of them take 20 lines of code or even more.
这里的所有答案都过于复杂，大多数都需要20行代码甚至更多。
This example uses just two lines of vanilla JavaScript, no lodash, underscore or other libraries:
这个例子只使用了两行普通的 JavaScript，没有 lodash、下划线或其他库：
let f = (a, b) => [].concat(...a.map(a => b.map(b => [].concat(a, b))));
let cartesian = (a, b, ...c) => b ? cartesian(f(a, b), ...c) : a;
Update:
更新：
This is the same as above but improved to strictly follow the Airbnb JavaScript Style Guide- validated using ESLintwith eslint-config-airbnb-base:
这与上面相同，但经过改进以严格遵循Airbnb JavaScript 风格指南- 使用ESLint和eslint-config-airbnb-base 进行验证：
const f = (a, b) => [].concat(...a.map(d => b.map(e => [].concat(d, e))));
const cartesian = (a, b, ...c) => (b ? cartesian(f(a, b), ...c) : a);
Special thanks to ZuBBfor letting me know about linter problems with the original code.
特别感谢ZuBB让我知道原始代码的linter问题。
Example
例子
This is the exact example from your question:
这是您问题中的确切示例：
let output = cartesian([1,2],[10,20],[100,200,300]);
Output
输出
This is the output of that command:
这是该命令的输出：
[ [ 1, 10, 100 ],
[ 1, 10, 200 ],
[ 1, 10, 300 ],
[ 1, 20, 100 ],
[ 1, 20, 200 ],
[ 1, 20, 300 ],
[ 2, 10, 100 ],
[ 2, 10, 200 ],
[ 2, 10, 300 ],
[ 2, 20, 100 ],
[ 2, 20, 200 ],
[ 2, 20, 300 ] ]
Demo
演示
See demos on:
请参阅以下演示：
- JS Bin with Babel(for old browsers)
- JS Bin without Babel(for modern browsers)
- 带有 Babel 的 JS Bin（适用于旧浏览器）
- 没有 Babel 的 JS Bin（适用于现代浏览器）
Syntax
句法
The syntax that I used here is nothing new. My example uses the spread operator and the rest parameters - features of JavaScript defined in the 6th edition of the ECMA-262 standard published on June 2015 and developed much earlier, better known as ES6 or ES2015. See:
我在这里使用的语法并不新鲜。我的示例使用扩展运算符和其余参数 - 2015 年 6 月发布的 ECMA-262 标准第 6 版中定义的 JavaScript 特性，并且开发得更早，更广为人知的是 ES6 或 ES2015。看：
- http://www.ecma-international.org/ecma-262/6.0/
- https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Functions/rest_parameters
- https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Operators/Spread_operator
- http://www.ecma-international.org/ecma-262/6.0/
- https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Functions/rest_parameters
- https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Operators/Spread_operator
It makes code like this so simple that it's a sin not to use it. For old platforms that don't support it natively you can always use Babel or other tools to transpile it to older syntax - and in fact my example transpiled by Babel is still shorter and simpler than most of the examples here, but it doesn't really matter because the output of transpilation is not something that you need to understand or maintain, it's just a fact that I found interesting.
它使这样的代码变得如此简单，以至于不使用它是一种罪过。对于原生不支持它的旧平台，您始终可以使用 Babel 或其他工具将其转译为旧语法——事实上，我的由 Babel 转译的示例仍然比这里的大多数示例更短更简单，但它没有真的很重要，因为转译的输出不是您需要理解或维护的东西，这只是我发现有趣的一个事实。
Conclusion
结论
There's no need to write hundred of lines of code that is hard to maintain and there is no need to use entire libraries for such a simple thing, when two lines of vanilla JavaScript can easily get the job done. As you can see it really pays off to use modern features of the language and in cases where you need to support archaic platforms with no native support of the modern features you can always use Babel or other tools to transpile the new syntax to the old one.
没有必要编写数百行难以维护的代码，也没有必要为这么简单的事情使用整个库，两行普通的 JavaScript 就可以轻松完成工作。如您所见，使用该语言的现代功能确实值得，如果您需要支持没有现代功能本机支持的古老平台，您可以随时使用 Babel 或其他工具将新语法转换为旧语法.
Don't code like it's 1995
不要像 1995 年那样编码
JavaScript evolves and it does so for a reason. TC39 does an amazing job of the language design with adding new features and the browser vendors do an amazing job of implementing those features.
JavaScript 的发展是有原因的。TC39 通过添加新功能在语言设计方面做得非常出色，而浏览器供应商在实现这些功能方面做得非常出色。
To see the current state of native support of any given feature in the browsers, see:
要查看浏览器中任何给定功能的本机支持的当前状态，请参阅：
To see the support in Node versions, see:
要查看 Node 版本的支持，请参阅：
To use modern syntax on platforms that don't support it natively, use Babel:
要在原生不支持现代语法的平台上使用现代语法，请使用 Babel：
回答by Danny
Here's a modified version of @viebel's code in plain Javascript, without using any library:
这是@viebel 代码的纯 Javascript 修改版本，不使用任何库：
function cartesianProduct(arr) {
return arr.reduce(function(a,b){
return a.map(function(x){
return b.map(function(y){
return x.concat([y]);
})
}).reduce(function(a,b){ return a.concat(b) },[])
}, [[]])
}
var a = cartesianProduct([[1, 2,3], [4, 5,6], [7, 8], [9,10]]);
console.log(JSON.stringify(a));回答by ckozl
it seems the community thinks this to be trivial and or easy to find a reference implementation, upon brief inspection i couldn't or maybe it's just that i like re-inventing the wheel or solving classroom-like programming problems either way its your lucky day:
社区似乎认为这是微不足道的，或者很容易找到参考实现，经过简短的检查，我不能，或者只是我喜欢重新发明轮子或解决课堂式的编程问题，无论哪种方式都是你的幸运日：
function cartProd(paramArray) {
function addTo(curr, args) {
var i, copy,
rest = args.slice(1),
last = !rest.length,
result = [];
for (i = 0; i < args[0].length; i++) {
copy = curr.slice();
copy.push(args[0][i]);
if (last) {
result.push(copy);
} else {
result = result.concat(addTo(copy, rest));
}
}
return result;
}
return addTo([], Array.prototype.slice.call(arguments));
}
>> console.log(cartProd([1,2], [10,20], [100,200,300]));
>> [
[1, 10, 100], [1, 10, 200], [1, 10, 300], [1, 20, 100],
[1, 20, 200], [1, 20, 300], [2, 10, 100], [2, 10, 200],
[2, 10, 300], [2, 20, 100], [2, 20, 200], [2, 20, 300]
]
full reference implementation that's relatively efficient... :-D
相对有效的完整参考实现...... :-D
on efficiency: you could gain some by taking the if out of the loop and having 2 separate loops since it is technically constant and you'd be helping with branch prediction and all that mess, but that point is kind of moot in javascript
关于效率：您可以通过将 if 移出循环并使用 2 个单独的循环来获得一些收益，因为它在技术上是恒定的，并且您将帮助进行分支预测和所有这些混乱，但这一点在 javascript 中没有实际意义
anywho, enjoy -ck
任何人，享受-ck
回答by le_m
The following efficient generator functionreturns the cartesian product of all given iterables:
// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
const remainder = tail.length > 0 ? cartesian(...tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}
// Example:
console.log(...cartesian([1, 2], [10, 20], [100, 200, 300]));It accepts arrays, strings, sets and all other objects implementing the iterable protocol.
它接受数组、字符串、集合和所有其他实现可迭代协议的对象。
Following the specification of the n-ary cartesian productit yields
遵循n 元笛卡尔积的规范，它产生
[]if one or more given iterables are empty, e.g.[]or''[[a]]if a single iterable containing a single valueais given.
[]如果一个或多个给定的可迭代对象为空，例如[]或''[[a]]如果给出了包含单个值的单个迭代a。
All other cases are handled as expected as demonstrated by the following test cases:
所有其他案例都按预期处理，如以下测试案例所示：
// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
const remainder = tail.length > 0 ? cartesian(...tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}
// Test cases:
console.log([...cartesian([])]); // []
console.log([...cartesian([1])]); // [[1]]
console.log([...cartesian([1, 2])]); // [[1], [2]]
console.log([...cartesian([1], [])]); // []
console.log([...cartesian([1, 2], [])]); // []
console.log([...cartesian([1], [2])]); // [[1, 2]]
console.log([...cartesian([1], [2], [3])]); // [[1, 2, 3]]
console.log([...cartesian([1, 2], [3, 4])]); // [[1, 3], [2, 3], [1, 4], [2, 4]]
console.log([...cartesian('')]); // []
console.log([...cartesian('ab', 'c')]); // [['a','c'], ['b', 'c']]
console.log([...cartesian([1, 2], 'ab')]); // [[1, 'a'], [2, 'a'], [1, 'b'], [2, 'b']]
console.log([...cartesian(new Set())]); // []
console.log([...cartesian(new Set([1]))]); // [[1]]
console.log([...cartesian(new Set([1, 1]))]); // [[1]]回答by sebnukem
Here's a non-fancy, straightforward recursive solution:
这是一个非花哨的，直接的递归解决方案：
function cartesianProduct(a) { // a = array of array
var i, j, l, m, a1, o = [];
if (!a || a.length == 0) return a;
a1 = a.splice(0, 1)[0]; // the first array of a
a = cartesianProduct(a);
for (i = 0, l = a1.length; i < l; i++) {
if (a && a.length) for (j = 0, m = a.length; j < m; j++)
o.push([a1[i]].concat(a[j]));
else
o.push([a1[i]]);
}
return o;
}
console.log(cartesianProduct([[1,2], [10,20], [100,200,300]]));
// [[1,10,100],[1,10,200],[1,10,300],[1,20,100],[1,20,200],[1,20,300],[2,10,100],[2,10,200],[2,10,300],[2,20,100],[2,20,200],[2,20,300]]回答by heenenee
Here is a recursive way that uses an ECMAScript 2015 generator functionso you don't have to create all of the tuples at once:
这是使用 ECMAScript 2015生成器函数的递归方式，因此您不必一次创建所有元组：
function* cartesian() {
let arrays = arguments;
function* doCartesian(i, prod) {
if (i == arrays.length) {
yield prod;
} else {
for (let j = 0; j < arrays[i].length; j++) {
yield* doCartesian(i + 1, prod.concat([arrays[i][j]]));
}
}
}
yield* doCartesian(0, []);
}
console.log(JSON.stringify(Array.from(cartesian([1,2],[10,20],[100,200,300]))));
console.log(JSON.stringify(Array.from(cartesian([[1],[2]],[10,20],[100,200,300]))));回答by Oriol
Using a typical backtracking with ES6 generators,
使用 ES6 生成器的典型回溯，
function cartesianProduct(...arrays) {
let current = new Array(arrays.length);
return (function* backtracking(index) {
if(index == arrays.length) yield current.slice();
else for(let num of arrays[index]) {
current[index] = num;
yield* backtracking(index+1);
}
})(0);
}
for (let item of cartesianProduct([1,2],[10,20],[100,200,300])) {
console.log('[' + item.join(', ') + ']');
}div.as-console-wrapper { max-height: 100%; }Below there is a similar version compatible with older browsers.
下面有一个与旧浏览器兼容的类似版本。
function cartesianProduct(arrays) {
var result = [],
current = new Array(arrays.length);
(function backtracking(index) {
if(index == arrays.length) return result.push(current.slice());
for(var i=0; i<arrays[index].length; ++i) {
current[index] = arrays[index][i];
backtracking(index+1);
}
})(0);
return result;
}
cartesianProduct([[1,2],[10,20],[100,200,300]]).forEach(function(item) {
console.log('[' + item.join(', ') + ']');
});div.as-console-wrapper { max-height: 100%; }回答by Christopher Moore
This is a pure ES6 solution using arrow functions
这是一个使用箭头函数的纯 ES6 解决方案
function cartesianProduct(arr) {
return arr.reduce((a, b) =>
a.map(x => b.map(y => x.concat(y)))
.reduce((a, b) => a.concat(b), []), [[]]);
}
var arr = [[1, 2], [10, 20], [100, 200, 300]];
console.log(JSON.stringify(cartesianProduct(arr)));回答by Fred Kleuver
Here is a one-liner using the native ES2019 flatMap. No libraries needed, just a modern browser (or transpiler):
这是使用原生 ES2019 的单行代码flatMap。不需要库，只需要一个现代浏览器（或转译器）：
data.reduce((a, b) => a.flatMap(x => b.map(y => [...x, y])), [[]]);
It's essentially a modern version of viebel's answer, without lodash.
它本质上是 viebel 答案的现代版本，没有 lodash。
