logo标签列表

JavaScript中多个数组的笛卡尔积

javascriptarraysalgorithmcartesian-product
178

你如何在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
可能是重复的问题：在循环中查找所有选项组合。 - Bergi
5
这是js-combinatorics模块中实现的：http://github.com/dankogai/js-combinatorics - Erel Segal-Halevi
1
可能是从n个包含m个元素的数组中生成组合的重复问题。 - Bergi
我同意underscore.js的观点，但我不确定删除函数式编程标签如何帮助@le_m。 - viebel
顺便提一下，d3在二月份添加了d3.cross(a, b[, reducer])。https://github.com/d3/d3-array#cross - Toph
显示剩余2条评论
36个回答
231

2020更新：使用纯JS的1行代码回答

原始2017年回答：使用纯JS的2行代码：（请参见下面的更新）

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

此示例仅使用两行纯JavaScript代码，没有lodash、underscore或其他库：

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 Style Guide - 使用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 建议使用 reduce。

特别感谢 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 ] ]

演示

查看以下演示：

语法

我在这里使用的语法并不新颖。 我的例子使用了展开运算符和剩余参数 - 这些是JavaScript中的特性，定义在ECMA-262标准的第6版中，该标准于2015年6月发布并在更早时期开发，被称为ES6或ES2015。请参见：

Update 2020示例中的新方法已在ES2019中添加： 这使得像这样的代码变得非常简单，不使用它就是一种罪过。对于不支持它的旧平台，您可以始终使用Babel或其他工具将其转换为较旧的语法 - 实际上，我的示例通过Babel转译后仍然比这里的大多数示例更短更简单，但这并不重要，因为转译的输出不是您需要理解或维护的内容，它只是我发现有趣的事实。
结论
没有必要编写数百行难以维护的代码，也没有必要为如此简单的事情使用整个库，当两行原生JavaScript可以轻松完成任务时。正如您所看到的，使用语言的现代特性确实很值得，并且在需要支持没有本地支持现代功能的古老平台的情况下，您始终可以使用Babel、TypeScript或其他工具将新语法转译为旧语法。
不要像1995年那样编码
JavaScript正在发展，这是有原因的。TC39通过添加新功能来进行语言设计，浏览器供应商通过实现这些功能来做出了惊人的工作。

要查看浏览器对任何特定功能的本地支持状态，请参见：

要查看Node版本的支持情况，请参见：

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

24
“不要像1995年那样编码” - 不必不友善，并非每个人都跟上了步伐。 - Godwhacker
14
当输入 ['a', 'b'], [1,2], [[9], [10]] 时，这段代码的效果不佳，它会产生以下结果：[ [ 'a', 1, 9 ], [ 'a', 1, 10 ], [ 'a', 2, 9 ], [ 'a', 2, 10 ], [ 'b', 1, 9 ], [ 'b', 1, 10 ], [ 'b', 2, 9 ], [ 'b', 2, 10 ] ]。也就是说，它不能保持 [[9], [10]] 中每个元素的类型。 - Redu
8
别写出2017年的代码了，使用.flatMap代替concat+map :-) - Bergi
4
把 a、b、d、e 这些名称留给你最喜欢的 JS 混淆器，有意义的名称可以帮助理解逻辑 :) 另外，c 去哪里了呢？不过这是一个很棒的解决方案，令人印象深刻！ - sp00m
4
我注意到你最新的 (...a) => a.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat()))); 在只有一个参数的情况下无法正常工作 -- 它不会返回一个嵌套数组，而是只返回原始输入的列表。 - Chris Smowton
显示剩余22条评论
93
这是一个解决问题的函数式解决方案（没有任何可变变量！），使用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);
    }, [ [] ]);
}

// [[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/启发。

这个答案中有一个错别字，不应该有一个", true"（也许自从您发帖以来lodash已经更改了？） - Chris Jefferson
@ChrisJefferson flatten函数的第二个参数是为了使扁平化变得浅层。在这里是必须的！ - viebel
4
抱歉，这是lodash / underscore不兼容的问题，它们交换了标志。 - Chris Jefferson
1
因此，在压平时，使用 underscore 的 true，使用 lodash 的 false 确保浅层压平。 - Akseli Palén
如何修改此函数以接受数组的数组？ - user4338202
显示剩余3条评论
60

这是@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));

2
由于将 ['gamma'] 扁平化为 'gamma' 和 [['alpha']] 扁平化为 ['alpha']，因此 cartesianProduct([[[1],[2],[3]], ['a', 'b'], [['gamma'], [['alpha']]], ['zii', 'faa']]) 失败。 - Lzh
因为使用.concat(y)而不是.concat([ y ])。 - Mulan
1
谢谢，您可以直接编辑答案而不是评论，我已经这样做了，所以现在不需要了 :P - Olivier Lalonde
43
下面这个高效的生成器函数会返回所有给定可迭代对象的笛卡尔积：

// 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]));
它接受数组、字符串、集合和所有实现可迭代协议的其他对象。

根据n元笛卡尔积的规范，如果一个或多个给定的可迭代对象为空，例如[]或''，则会产生以下结果：

  • []
    • 如果一个或多个给定的可迭代对象为空，例如[]或''
  • [[a]]如果给定一个包含单个值a的单个可迭代对象。

所有其他情况都按预期处理，如下面的测试用例所示：

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

你介意解释一下这个是怎么回事吗？非常感谢！ - LeandroP
1
感谢您教给我们一个非常棒的例子，使用生成器函数+尾递归+双层循环！但是代码中第一个for循环的位置需要更改，以使输出子数组的顺序正确。修正后的代码：function* cartesian(head, ...tail) { for (let h of head) { const remainder = tail.length > 0 ? cartesian(...tail) : [[]]; for (let r of remainder) yield [h, ...r] } } - ooo
1
如果你想要复制 OP 评论中给出的笛卡尔积元组的顺序，那么你的修改是正确的。然而，在积中元组的顺序通常是不相关的，例如在数学上结果是一个无序集合。我选择了这个顺序，因为它需要更少的递归调用，因此更具性能 - 尽管我没有运行基准测试。 - le_m
勘误：在我上面的评论中，“尾递归”应该是“递归”（不是尾调用）。 - ooo
我传入一个Map时得到了错误的结果，除非我先使用Array.from或[...arg]克隆可迭代对象。也许问题出在我身上。 - ninjagecko
2
我最喜欢这个版本，无论如何。它使用了生成器，与最受欢迎的答案一样紧凑（比被接受的答案更紧凑），同时使用易读的变量名。到目前为止，这是我尝试过的唯一一个不会展平嵌套数组的答案，而这是其他答案的不良副作用！唯一的“缺点”是顺序不同，但对我来说真的不是问题。 - panda-byte
31

看起来社区认为这是微不足道的和/或很容易找到一个参考实现。然而，经过简短的检查，我找不到一个，... 要么是因为我喜欢重复发明轮子或解决课堂式的编程问题。无论哪种方式都是你的幸运日：

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

这是一个相对高效的完整参考实现...

关于效率：你可以通过将if语句移出循环并使用两个独立的循环获得一些效率，因为这在技术上是常数，并且有助于分支预测和所有混乱的事情，但在JavaScript中这个点有点无关紧要。

1
感谢@ckoz提供详细的答案。为什么不使用数组的reduce函数呢？ - viebel
2
@viebel 你为什么想要使用reduce？首先，reduce在旧版浏览器上的支持非常差（参见：https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array/Reduce），而且无论如何，那个其他答案中的疯狂代码对你来说真的看起来可读吗？对我来说不是。当然它更短，但一旦被压缩，这段代码的长度将与其他解决方案相同，更易于调试/优化。其次，所有这些“reduce”解决方案都归结为相同的问题，除了它们具有闭包查找（理论上较慢），还更难设计以处理无限集合... - ckozl
7
我创建了一个速度更快，代码更简洁的版本（我个人认为）：http://pastebin.com/YbhqZuf7。它通过不使用`result = result.concat(...)和args.slice(1)来实现速度提升。不幸的是，我无法找到一种方法来摆脱curr.slice()`和递归。 - Pauan
2
@Pauan 做得好，整体上热点问题减少了不少，根据我所看到的情况，性能提升了10%-50%。但是我无法评论“清晰度”，因为我觉得你的版本由于使用闭包作用域变量而更难以理解。但总的来说，更高效的代码往往更难以理解。我最初编写原始版本是为了可读性，但我希望有更多时间与你进行性能比拼；）也许以后吧... - ckozl
这确实是那些问题之一。 - Tegra Detra
@Pauan - 最好在这里发布您的代码作为答案。链接会失效。;-) - RobG
25
这是一个简单直接的递归解决方案： 

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

2
这个代码在这个主题下是最有效的纯JS代码。它需要大约600毫秒的时间来完成对3个100项数组的处理，生成一个长度为1M的数组。 - Redu
2
在不展平原始值的情况下，适用于cartesianProduct（[[[1]，[2]，[3]]，['a'，'b']，[['gamma']，[['alpha']]]，['zii'，'faa']]）; - Lzh
21

使用ES2019原生的flatMap函数可以轻松实现一行代码。无需任何库，只需使用现代浏览器（或转译器）即可：

data.reduce((a, b) => a.flatMap(x => b.map(y => [...x, y])), [[]]);

它本质上是 viebel 的答案的现代版本，没有使用 lodash。

当然不需要使用库。但这也不是最易读的代码。这是一个权衡。 - Arturo Hernandez
可读性在这种情况下更多地与我选择使用扩展运算符有关，而不是选择不使用库。我认为lodash并不会导致更可读的代码。 - Fred Kleuver
我更喜欢这个答案，而不是rsp的最受欢迎的答案中的2020版本，因为当只给出一个数组时，例如 data = [["hello"]]，它也可以正确地工作。 - trincot
2
可读性也与变量名有关。a、b、x和y都是通用的非描述性名称。如果使用实际描述性名称，可读性将会提高。arrays.reduce((product, array) => product.flatMap(combination => array.map(item => [...combination, item])), [[]])尽管如此，你可以看到它变得有点长了。 - 3limin4t0r
14

函数式编程

这个问题被标记为函数式编程，所以让我们来看一下列表单子：

这个单子列表的一个应用是表示非确定性计算。在算法中，列表 可以保存所有执行路径的结果...

嗯，听起来很完美适合使用笛卡尔积。JavaScript给了我们数组，而单子绑定函数是Array.prototype.flatMap，所以让我们把它们用起来-

const cartesian = (...all) => {
  const loop = (t, a, ...more) =>
    a === undefined
      ? [ t ]
      : a.flatMap(x => loop([ ...t, x ], ...more))
  return loop([], ...all)
}

console.log(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]

更多递归
其他递归实现包括 - 

const cartesian = (a, ...more) =>
  a == null
    ? [[]]
    : cartesian(...more).flatMap(c => a.map(v => [v,...c]))

for (const p of cartesian([1,2], [10,20], [100,200,300]))
  console.log(JSON.stringify(p))
.as-console-wrapper { min-height: 100%; top: 0; }

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

请注意上面的不同顺序。通过交换两个循环，您可以得到字典顺序。在循环中避免重复调用cartesian，就像Nick's answer所示-

const bind = (x, f) => f(x)

const cartesian = (a, ...more) =>
  a == null
    ? [[]]
    : bind(cartesian(...more), r => a.flatMap(v => r.map(c => [v,...c])))

for (const p of cartesian([1,2], [10,20], [100,200,300]))
  console.log(JSON.stringify(p))
.as-console-wrapper { min-height: 100%; top: 0; }

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

生成器
另一个选择是使用生成器。生成器非常适合组合数学问题，因为解空间可能非常大。生成器提供惰性求值，因此可以随时暂停、恢复或取消操作。 

function* cartesian(a, ...more) {
  if (a == null) return yield []
  for (const v of a)
    for (const c of cartesian(...more)) // ⚠️
      yield [v, ...c]
}
  
for (const p of cartesian([1,2], [10,20], [100,200,300]))
  console.log(JSON.stringify(p))
.as-console-wrapper { min-height: 100%; top: 0; }

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

也许你注意到我们在生成器中的循环中调用了cartesian。如果你觉得这可以优化，那是可以的！在这里，我们使用了一个通用的tee函数，它可以将任何迭代器分叉n次。
function* cartesian(a, ...more) {
  if (a == null) return yield []
  for (const t of tee(cartesian(...more), a.length)) // ✅
    for (const v of a)
      for (const c of t) // ✅
        yield [v, ...c]
}

在这里，tee的实现方式是 -

function tee(g, n = 2) {
  const memo = []
  function* iter(i) {
    while (true) {
      if (i >= memo.length) {
        const w = g.next()
        if (w.done) return
        memo.push(w.value)
      }
      else yield memo[i++]
    }
  }
  return Array.from(Array(n), _ => iter(0))
}

即使在小规模测试中，使用tee实现的cartesian生成器的性能也是原来的两倍。
13

下面是一种递归方法，使用了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]))));

当其中一个数组具有类似于cartesian([[1],[2]],[10,20],[100,200,300])的数组项时，这将无法工作。 - Redu
@Redu的答案已更新，支持数组参数。 - heenenee
是的，.concat() 内置的展开运算符有时可能会变得棘手。 - Redu
12

这是一个纯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)));

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接