JavaScript中多个数组的笛卡尔积

Question

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

举个例子,

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

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);
    }, [ [] ]);
}

// [[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']));  

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

Answer 2

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

这里的所有答案都过于复杂,大多数都需要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问题.

例

这是您问题的确切示例:

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(适用于现代浏览器)

句法

我在这里使用的语法并不新鲜.我的例子使用了扩展运算符和其余参数 - 在2015年6月发布的第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描述的例子仍然比这里的大多数示例更简单,更简单,但它没有真的很重要,因为翻译的输出不是你需要理解或维护的东西,这只是我发现有趣的事实.

结论

没有必要编写数百行难以维护的代码,并且当两行vanilla JavaScript可以轻松完成工作时,不需要将整个库用于这么简单的事情.正如您所看到的,使用该语言的现代功能确实是值得的,如果您需要支持没有现代功能原生支持的古老平台,您可以始终使用Babel或其他工具将旧语法转换为旧语法.

不要像1995年那样编码

JavaScript发展,它出于某种原因这样做.TC39通过添加新功能在语言设计方面做得非常出色,浏览器供应商在实现这些功能方面做得非常出色.

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

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

要查看Node版本中的支持,请参阅:

• http://node.green/

要在不支持本机的平台上使用现代语法,请使用Babel:

• https://babeljs.io/

Answer 3

这里是普通Javascript中@ viebel代码的修改版本,不使用任何库:

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));

Answer 4

似乎社区认为这是微不足道的,或者很容易找到参考实现,经过简单的检查我不能或者也许只是因为我喜欢重新发明轮子或解决课堂式的编程问题,无论是你的幸运日:

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

关于效率:你可以通过将if取出循环并拥有2个单独的循环来获得一些,因为它在技术上是恒定的,你将帮助分支预测和所有这些混乱,但这一点在javascript中有点没有用

任何人,享受-ck

Answer 5

以下高效的生成器函数返回所有给定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]));

它接受实现可迭代协议的数组,字符串,集和所有其他对象.

按照n-ary笛卡儿产品的规格,它产生

• []如果一个或多个给定的可迭代物为空,例如[]或''
• [[a]]如果给出了包含单个值的单个iterable 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]]

Answer 6

这是一个非常花哨,直截了当的递归解决方案:

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 7

这是使用原生 ES2019 的单行代码flatMap。不需要库，只需要一个现代浏览器（或转译器）：

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

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

Answer 8

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

下面是与旧版浏览器兼容的类似版本.

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

Answer 9

这是一种使用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 10

带有lodash的coffeescript版本:

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

Answer 11

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

单行方法，可通过缩进更好地阅读。

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

它需要一个带有所需笛卡尔项数组的数组。

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

var data = [[1, 2], [10, 20], [100, 200, 300]],
    result = data.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));

console.log(result.map(a => a.join(' ')));

Answer 13

这被标记为函数编程，所以让我们看一下List monad：

该单子列表的一个应用程序代表不确定性计算。List 可以保存算法中所有执行路径的结果 ...

那么这听起来像一个完美的适合cartesian。JavaScript提供了我们Array，而monadic绑定函数是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]))

代替loop上面的，t可以添加为咖喱参数-

const makeCartesian = (t = []) => (a, ...more) =>
  a === undefined
    ? [ t ]
    : a .flatMap (x => makeCartesian ([ ...t, x ]) (...more))

const cartesian =
  makeCartesian ()

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

Answer 14

另一个更简化的 2021 年风格答案，仅使用 reduce、map 和 concat 方法：

const cartesian = (...arr) => arr.reduce((a,c) => a.map(e => c.map(f => e.concat([f]))).reduce((a,c) => a.concat(c), []), [[]]);

console.log(cartesian([1, 2], [10, 20], [100, 200, 300]));