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个回答
9

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

8

使用lodash的Coffeescript版本：

_ = require("lodash")
cartesianProduct = ->
    return _.reduceRight(arguments, (a,b) ->
        _.flatten(_.map(a,(x) -> _.map b, (y) -> x.concat(y)), true)
    , [ [] ])
8
一种单行缩进的方法，更易于阅读。
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(' ')));
.as-console-wrapper { max-height: 100% !important; top: 0; }

1
我不得不添加一个守卫语句来正确处理数组只有一个元素的情况：if (arr.length === 1) return arr[0].map(el => [el]); - JacobEvelyn
4
在我的特定环境中，“老派”的方法似乎比基于更现代功能的方法更有效。以下是代码（包括与@rsp和@sebnukem在此线程中发布的其他解决方案的小比较），如果对其他人有用，应该会很有用。
思路如下。假设我们正在构造N个数组a_1，...，a_N的外积，每个数组都有m_i个组件。这些数组的外积具有M=m_1*m_2*...*m_N个元素，我们可以将其中的每个元素与一个N-维向量相对应，其分量为正整数，并且第i个分量严格受到上限m_i的限制。例如，向量(0,0，...，0)将对应于从每个数组中取第一个元素的特定组合，而(m_1-1,m_2-1，...，m_N-1)则与从每个数组中取最后一个元素的组合相对应。因此，为了构造所有M个组合，下面的函数依次构造所有这样的向量，并针对每个向量确定输入数组的相应组合。
function cartesianProduct(){
    const N = arguments.length;

    var arr_lengths = Array(N);
    var digits = Array(N);
    var num_tot = 1;
    for(var i = 0; i < N; ++i){
        const len = arguments[i].length;
        if(!len){
            num_tot = 0;
            break;
        }
        digits[i] = 0;
        num_tot *= (arr_lengths[i] = len);
    }

    var ret = Array(num_tot);
    for(var num = 0; num < num_tot; ++num){

        var item = Array(N);
        for(var j = 0; j < N; ++j){ item[j] = arguments[j][digits[j]]; }
        ret[num] = item;

        for(var idx = 0; idx < N; ++idx){
            if(digits[idx] == arr_lengths[idx]-1){
                digits[idx] = 0;
            }else{
                digits[idx] += 1;
                break;
            }
        }
    }
    return ret;
}
//------------------------------------------------------------------------------
let _f = (a, b) => [].concat(...a.map(a => b.map(b => [].concat(a, b))));
let cartesianProduct_rsp = (a, b, ...c) => b ? cartesianProduct_rsp(_f(a, b), ...c) : a;
//------------------------------------------------------------------------------
function cartesianProduct_sebnukem(a) {
    var i, j, l, m, a1, o = [];
    if (!a || a.length == 0) return a;

    a1 = a.splice(0, 1)[0];
    a = cartesianProduct_sebnukem(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;
}
//------------------------------------------------------------------------------
const L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
const args = [L, L, L, L, L, L];

let fns = {
    'cartesianProduct': function(args){ return cartesianProduct(...args); },
    'cartesianProduct_rsp': function(args){ return cartesianProduct_rsp(...args); },
    'cartesianProduct_sebnukem': function(args){ return cartesianProduct_sebnukem(args); }
};

Object.keys(fns).forEach(fname => {
    console.time(fname);
    const ret = fns[fname](args);
    console.timeEnd(fname);
});

使用node v6.12.2，我得到以下时间:

cartesianProduct: 427.378ms
cartesianProduct_rsp: 1710.829ms
cartesianProduct_sebnukem: 593.351ms
好东西，有时笛卡尔积可能涉及到巨大的输入/输出，大多数基于递归的方法都会失败。即使将一个超过4GB的疯狂大对象放入内存中，如果不使用生成器，也会失败。这种普通的方法是可行的。 - Valen
4

用几行现代JavaScript代码实现功能，无需使用类库或依赖项，如Lodash。

function cartesian(...arrays) {
  return arrays.reduce((a, b) => a.flatMap(x => b.map(y => x.concat([y]))), [ [] ]);
}

console.log(
  cartesian([1, 2], [10, 20], [100, 200, 300])
    .map(arr => JSON.stringify(arr))
    .join('\n')
);

4
您可以使用reduce函数来对二维数组进行处理。在每次循环中，使用flatMap函数获取累加器数组中的acc.length x curr.length个组合结果。由于在第一次迭代时c是一个数字，在后续迭代中是一个数组，因此需要使用[].concat(c, n)来处理。 

const data = [ [1, 2], [10, 20], [100, 200, 300] ];

const output = data.reduce((acc, curr) =>
  acc.flatMap(c => curr.map(n => [].concat(c, n)))
)

console.log(JSON.stringify(output))

(This is based on Nina Scholz's answer)

4

以下是使用 reduce、map 和 concat 方法的另一种更简化的 2021 风格答案：

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

说实话，我不知道这里发生了什么，但它似乎对于复杂对象也能正常工作（不像某些只适用于字符串的解决方案）。我希望您使用一些更具描述性的名称（而不是a、c、f等）-特别是它们彼此重叠。我的意思是它们有不同的作用域，但是相同的名称，所以很难理解。 - WrRaThY
附带 TypeScript 类型也不错，所以输入应该是 Array<Array<any>>（对于其他变量也是如此），而不是什么都没有。 - WrRaThY
4
这是一个使用仅 flatMap 和 map 的递归单行代码： 

const inp = [
  [1, 2],
  [10, 20],
  [100, 200, 300]
];

const cartesian = (first, ...rest) => 
  rest.length ? first.flatMap(v => cartesian(...rest).map(c => [v].concat(c))) 
              : first;

console.log(cartesian(...inp));

4

对于那些需要TypeScript的人（重新实现了@Danny的答案）

/**
 * Calculates "Cartesian Product" sets.
 * @example
 *   cartesianProduct([[1,2], [4,8], [16,32]])
 *   Returns:
 *   [
 *     [1, 4, 16],
 *     [1, 4, 32],
 *     [1, 8, 16],
 *     [1, 8, 32],
 *     [2, 4, 16],
 *     [2, 4, 32],
 *     [2, 8, 16],
 *     [2, 8, 32]
 *   ]
 * @see https://dev59.com/xWct5IYBdhLWcg3wKqQd#36234242
 * @see https://en.wikipedia.org/wiki/Cartesian_product
 * @param arr {T[][]}
 * @returns {T[][]}
 */
function cartesianProduct<T> (arr: T[][]): T[][] {
  return arr.reduce((a, b) => {
    return a.map(x => {
      return b.map(y => {
        return x.concat(y)
      })
    }).reduce((c, d) => c.concat(d), [])
  }, [[]] as T[][])
}
这只支持同质类型; 数组中所有的值都是相同类型的。 - Martijn Pieters
3
一种更易读的实现 

function productOfTwo(one, two) {
  return one.flatMap(x => two.map(y => [].concat(x, y)));
}

function product(head = [], ...tail) {
  if (tail.length === 0) return head;
  return productOfTwo(head, product(...tail));
}

const test = product(
  [1, 2, 3],
  ['a', 'b']
);

console.log(JSON.stringify(test));

[].concat(x, y) 也可以写成 [x, y].flat()。此外，我们还可以使用 [[1, 2, 3], ['a', 'b']].reduce(productOfTwo) 来避免递归。 - Trevor Dixon
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接