仅用两行代码实现笛卡尔积，高效解决商品类型组合问题

662

code

Posted on：Sep 1, 2020

笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尔积（Cartesian product），又称直积，表示为X × Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。

使用场景

在程序设计领域笛卡尔乘积多用于多个属性组合描述某事物，例如在线购物时通过颜色、容量、重量来选择一部手机：

const source = [
  ['红', '黄', '蓝'],
  ['64G', '128G', '256G'],
  ['30kg', '100kg', '5kg'],
]

我们可以通过该数组组合得到 红-128G-100kg 这样一台手机，该数组可以组合出 27 种不同的配置，那么这个组合的过程我们就可以用笛卡尔乘积来处理。

思路解析

首先申明笛卡尔乘积函数，用于将两个一维数组进行组合：

1	const cartesianProduct = (prev, next) => prev.reduce((result, p) => [...result, ...next.map(n => p + n)], [])

然后遍历数据源，将数组种的前两个元素带入到上面的函数得出一个新的数组，再把得到的数组与第三个元素带入，以此迭代得到最终的结果:

1	source.reduce((result, item, i) => (i > 0 ? cartesianProduct(result, item) : result), source[0])

得益于 javascript 对数组操作的便利性，我们可以写出比大多数语言都要少量的代码

完整代码

const source = [
  ['红', '黄', '蓝'],
  ['64G', '128G', '256G'],
  ['4C', '8C', '16C'],
]

const cartesianProduct = (prev, next) => prev.reduce((result, p) => [...result, ...next.map(n => p + n)], [])
const r = source.reduce((result, item, i) => (i > 0 ? cartesianProduct(result, item) : result), source[0])

console.log(r)

运行效果

结果二维数组版

更新于 2022-03-04

1	const cartesianProduct = s => s.reduce((p, c, i) => i > 0 ? p.reduce((r, p) => r.concat(c.map(n => [p].flat().concat(n))), []) : c.map(n => [n]), [])

效果

// index.js
const cartesianProduct = s => s.reduce((p, c, i) => i > 0 ? p.reduce((r, p) => r.concat(c.map(n => [p].flat().concat(n))), []) : c.map(n => [n]), [])

console.log(cartesianProduct([
  ['粉', '黄', '蓝'],
  ['64G', '128G', '256G'],
  ['4C', '8C', '16C'],
]))
console.log('-----分割线------')
console.log(cartesianProduct([['粉', '黄', '蓝']]))

$ node index.js
[
  [ '粉', '64G', '4C' ],   [ '粉', '64G', '8C' ],
  [ '粉', '64G', '16C' ],  [ '粉', '128G', '4C' ],
  [ '粉', '128G', '8C' ],  [ '粉', '128G', '16C' ],
  [ '粉', '256G', '4C' ],  [ '粉', '256G', '8C' ],
  [ '粉', '256G', '16C' ], [ '黄', '64G', '4C' ],
  [ '黄', '64G', '8C' ],   [ '黄', '64G', '16C' ],
  [ '黄', '128G', '4C' ],  [ '黄', '128G', '8C' ],
  [ '黄', '128G', '16C' ], [ '黄', '256G', '4C' ],
  [ '黄', '256G', '8C' ],  [ '黄', '256G', '16C' ],
  [ '蓝', '64G', '4C' ],   [ '蓝', '64G', '8C' ],
  [ '蓝', '64G', '16C' ],  [ '蓝', '128G', '4C' ],
  [ '蓝', '128G', '8C' ],  [ '蓝', '128G', '16C' ],
  [ '蓝', '256G', '4C' ],  [ '蓝', '256G', '8C' ],
  [ '蓝', '256G', '16C' ]
]
-----分割线------
[ [ '粉' ], [ '黄' ], [ '蓝' ] ]