JavaScript 中多个数组的笛卡尔积2020年更新：1行（！）答案与香草JS

javascript arrays algorithm cartesian-product

2022-08-30 02:19:05

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

例如，

cartesian([1, 2], [10, 20], [100, 200, 300])

应该返回

[
  [1, 10, 100],
  [1, 10, 200],
  [1, 10, 300],
  [2, 10, 100],
  [2, 10, 200]
  ...
]

答案 1

2020年更新：1行（！）答案与香草JS

原始2017答案：2行答案与香草JS：（见下面的更新）

这里的所有答案都过于复杂，其中大多数需要20行代码甚至更多。

此示例仅使用两行 vanilla 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问题。

2020年更新：

自从我写了这个答案以来，我们得到了更好的内置功能，这最终可以让我们将代码减少到只有1行！

const cartesian =
  (...a) => a.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat())));

特别感谢inker建议使用减少。

特别感谢Bergi建议使用新添加的flatMap。

特别感谢 ECMAScript 2019 为该语言添加了 flat 和 flatMap！

例

这是您问题中的确切示例：

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

演示

观看演示：

带有 Babel 的 JS Bin（适用于旧浏览器）
没有 Babel 的 JS Bin（适用于现代浏览器）

语法

我在这里使用的语法并不是什么新鲜事。我的示例使用 spread 运算符和 rest 参数 - JavaScript 的功能在 2015 年 6 月发布的 ECMA-262 标准的第 6 版中定义，并且开发得更早，更广为人知的是 ES6 或 ES2015。看：

ES2019 中添加了 Update 2020 示例中的新方法：

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

结论

没有必要编写数百行难以维护的代码，也没有必要使用整个库来完成如此简单的事情，当两行vanilla JavaScript可以轻松完成工作时。正如你所看到的，使用该语言的现代功能确实是值得的，并且在你需要支持没有现代功能的原生支持的古老平台的情况下，你可以随时使用Babel，TypeScript或其他工具将新语法转换为旧语法。

不要像1995年那样编码

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

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

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

http://node.green/

要在本机不支持现代语法的平台上使用现代语法，请使用 Babel 或 TypeScript：

答案 2

下面是问题的函数式解决方案（没有任何可变变量！）使用和，由提供：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>

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