JavaScript中多个数组的笛卡尔积

你将如何在JavaScript中实现多个数组的笛卡尔积？

举个例子，

cartesian([1,2],[10,20],[100,200,300]) //should be // [[1,10,100],[1,10,200],[1,10,300],[2,10,100],[2,10,200]...] 

Answer 1

下面是使用reduce和flatten （由underscore.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); }, [ [] ]); }; cartesianProductOf([1, 2], [3, 4], ['a', 'b']); // [[1,3,"a"],[1,3,"b"],[1,4,"a"],[1,4,"b"],[2,3,"a"],[2,3,"b"],[2,4,"a"],[2,4,"b"]] 

备注：此解决方案的灵感来自http://cwestblog.com/2011/05/02/cartesian-product-of-multiple-arrays/

Answer 2

这里是一个修改版本的@ 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(a); 

Answer 3

似乎社区认为这是微不足道的，或容易找到一个参考实现，经过简短的检查，我不能或者也许只是我喜欢重新发明轮子或解决教室般的编程问题，无论是你的幸运日：

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

全面的参考实现，相对高效…： – D.

在效率上：你可以通过如果从循环中获得一些，并有2个独立的循环，因为它在技术上是恒定的，你会帮助分支预测和所有的混乱，但这一点是有点没有意义的JavaScript

anywho，enjoy -ck

Answer 4

2017更新：与香草JS的2行答案

这里所有的答案都太复杂了 ，大部分都是20行代码甚至更多。

这个例子只使用了两行香草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; 

更新：

这与上面相同，但改进后严格遵循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); 

特别感谢ZuBB让我知道原始代码的linter问题。

例

这是你的问题的确切例子：

 let output = cartesian([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 ] ] 

演示

请参阅以下演示：

• 与巴别的JS斌 （旧版浏览器）
• 没有巴别塔的JS Bin （适合现代浏览器）

句法

我在这里使用的语法并不新鲜。 我的例子使用了扩展运算符和其他参数 – 在2015年6月发布的ECMA-262标准的第六版中定义的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

它使这样的代码变得如此简单，以至于不使用它是一种罪过。 对于本来不支持它的旧平台，你总是可以使用Babel或其他工具将其转换为较旧的语法 – 事实上，我的Babel传输的例子比这里的大多数例子更短更简单，但是它并不真的很重要，因为我们并不需要理解或维护这些转译的输出，这只是一个事实，我发现它很有趣。

结论

不需要编写上百行难以维护的代码，而且当两行香草JavaScript可以轻松完成工作时，不需要使用整个库来完成这样简单的任务。 正如您所看到的，使用该语言的现代功能确实值得您付出代价，并且在您需要支持没有现代功能的本机支持的古老平台的情况下，您始终可以使用Babel或其他工具将新语法转换为旧语法。

不要像1995年那样编码

JavaScript的发展，这是有原因的。 TC39在语言设计方面做得非常出色，增加了新功能，浏览器厂商在实现这些功能方面做得非常出色。

要查看浏览器中任何给定功能的本机支持的当前状态，请参阅：

• http://caniuse.com/
• https://kangax.github.io/compat-table/

要查看Node版本中的支持，请参阅：

• http://node.green/

要在原生不支持的平台上使用现代语法，请使用Babel：

• https://babeljs.io/

Answer 5

这是一个非花哨的，简单的递归解决方案：

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

Answer 6

下面是使用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])))); 

Answer 7

使用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%; } 

Answer 8

这是一个使用箭头功能的纯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))); 

Answer 9

与lodash coffeescript版本：

 _ = require("lodash") cartesianProduct = -> return _.reduceRight(arguments, (a,b) -> _.flatten(_.map(a,(x) -> _.map b, (y) -> x.concat(y)), true) , [ [] ]) 

Answer 10

当任何输入数组包含一个数组项时，这个主题下的一些答案会失败。 你最好检查一下。

无论如何不需要下划线，不管什么。 我相信这个应该用纯JS JS6来完成，就像它的功能一样。

这段代码使用了一个reduce和一个嵌套的map，只是为了获得两个数组的笛卡尔乘积，但是第二个数组来自一个少数组的同一个函数的递归调用; 因此.. a[0].cartesian(...a.slice(1))

 Array.prototype.cartesian = function(...a){ return a.length ? this.reduce((p,c) => (p.push(...a[0].cartesian(...a.slice(1)).map(e => a.length > 1 ? [c,...e] : [c,e])),p),[]) : this; }; var arr = ['a', 'b', 'c'], brr = [1,2,3], crr = [[9],[8],[7]]; console.log(JSON.stringify(arr.cartesian(brr,crr))); 

Answer 11

以下高效生成器函数返回所有给定迭代的笛卡尔乘积：

 // Return cartesian product of given iterables: function* cartesian(head, ...tail) { const remaining = tail.length > 0 ? cartesian(...tail) : [[]]; for (let r of remaining) for (let h of head) yield [h, ...r]; } // Example: console.log(...cartesian([1, 2], [10, 20], [100, 200, 300])); 

Answer 12

一种非递归方法，可以在将产品实际添加到结果集之前添加过滤和修改产品的功能。 请注意使用.map而不是.forEach。 在某些浏览器中，.map运行速度更快。

 function crossproduct(arrays,rowtest,rowaction) { // Calculate the number of elements needed in the result var result_elems = 1, row_size = arrays.length; arrays.map(function(array) { result_elems *= array.length; }); var temp = new Array(result_elems), result = []; // Go through each array and add the appropriate element to each element of the temp var scale_factor = result_elems; arrays.map(function(array) { var set_elems = array.length; scale_factor /= set_elems; for(var i=result_elems-1;i>=0;i--) { temp[i] = (temp[i] ? temp[i] : []); var pos = i / scale_factor % set_elems; // deal with floating point results for indexes, this took a little experimenting if(pos < 1 || pos % 1 <= .5) { pos = Math.floor(pos); } else { pos = Math.min(array.length-1,Math.ceil(pos)); } temp[i].push(array[pos]); if(temp[i].length===row_size) { var pass = (rowtest ? rowtest(temp[i]) : true); if(pass) { if(rowaction) { result.push(rowaction(temp[i])); } else { result.push(temp[i]); } } } } }); return result; } 

Answer 13

我注意到，没有人发布一个解决方案，允许传递一个函数来处理每个组合，所以这里是我的解决方案：

 const _ = require('lodash') function combinations(arr, f, xArr = []) { return arr.length>1 ? _.flatMap(arr[0], x => combinations(arr.slice(1), f, xArr.concat(x))) : arr[0].map(x => f(...xArr.concat(x))) } // use case const greetings = ["Hello", "Goodbye"] const places = ["World", "Planet"] const punctuationMarks = ["!", "?"] combinations([greetings,places,punctuationMarks], (greeting, place, punctuationMark) => `${greeting} ${place}${punctuationMark}`) .forEach(row => console.log(row)) 

输出：

 Hello World! Hello World? Hello Planet! Hello Planet? Goodbye World! Goodbye World? Goodbye Planet! Goodbye Planet?