如何在 Javascript 中生成来自多个对象的项目的所有组合

Question

我有一组带有名称和选项的对象，我需要所有可能的产品组合。重要的是这个数组有 N 个对象，每个对象都有 N 个选项。

我试图创建某种递归算法，但问题是我最终未能递归推送以接收所需的数据结构。我也尝试了 Cartesian product of multiple arrays in JavaScript 的方法，但它似乎与所需的输出无关。

示例：

input = [
    {
        name: "Size",
        options: [ { value: "S" }, { value: "M" }, { value: "L" }, ...and so on]
    },
    {
        name: "Color",
        options: [ { value: "Red" }, { value: "White" }, { value: "Blue" }, ...and so on]
    },
    {
        name: "Weight",
        options: [ { value: "1kg" }, { value: "2kg" }, { value: "3kg" }, { value: "4kg"}, ]
    },
    .... and so on
];

我需要以数组的形式获得所有可能的组合，该数组本身包含一个对象数组以及对象的名称和值。

示例（数组的数组）：

    output = [ 
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'Red'}, {name: 'Weight', value: '1kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'Red'}, {name: 'Weight', value: '2kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'Red'}, {name: 'Weight', value: '3kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'Red'}, {name: 'Weight', value: '4kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'White'}, {name: 'Weight', value: '1kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'White'}, {name: 'Weight', value: '2kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'White'}, {name: 'Weight', value: '3kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'White'}, {name: 'Weight', value: '4kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'Blue'}, {name: 'Weight', value: '1kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'Blue'}, {name: 'Weight', value: '2kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'Blue'}, {name: 'Weight', value: '3kg'} ],
    [ {name: 'Size', value: 'S'}, {name: 'Color', value: 'Blue'}, {name: 'Weight', value: '4kg'} ],
    [ {name: 'Size', value: 'M'}, {name: 'Color', value: 'Red'}, {name: 'Weight', value: '1kg'} ],
    [ {name: 'Size', value: 'M'}, {name: 'Color', value: 'Red'}, {name: 'Weight', value: '2kg'} ],
    [ {name: 'Size', value: 'M'}, {name: 'Color', value: 'Red'}, {name: 'Weight', value: '3kg'} ],
    [ {name: 'Size', value: 'M'}, {name: 'Color', value: 'Red'}, {name: 'Weight', value: '4kg'} ],
    [ {name: 'Size', value: 'M'}, {name: 'Color', value: 'White'}, {name: 'Weight', value: '1kg'} ],
    [ {name: 'Size', value: 'M'}, {name: 'Color', value: 'White'}, {name: 'Weight', value: '2kg'} ],
    [ {name: 'Size', value: 'M'}, {name: 'Color', value: 'White'}, {name: 'Weight', value: '3kg'} ],
    [ {name: 'Size', value: 'M'}, {name: 'Color', value: 'White'}, {name: 'Weight', value: '4kg'} ],
    ... and so on 
];

Answer 1

更新：根据 Mulan 的建议修复了第一个 cartesian 实现。

这绝对是一道笛卡尔积题。唯一的问题是您需要在调用笛卡尔积之前格式化您的输入。这是一个版本，使用一个简单的递归 cartesian 函数。

const cartesian = ([xs, ...xss]) =>
  xs == undefined
    ? [[]]
  : xs .flatMap (x => cartesian (xss) .map (ys => [x, ...ys]))

const combine = (properties) =>
  cartesian (properties .map (({name, options}) => options .map (({value}) => ({name, value}))))

const properties = [{name: "Size", options: [ { value: "S" }, { value: "M" }, { value: "L" }, /*...and so on */]}, {name: "Color", options: [ { value: "Red" }, { value: "White" }, { value: "Blue" }, /*...and so on */]}, {name: "Weight", options: [ { value: "1kg" }, { value: "2kg" }, { value: "3kg" }, { value: "4kg"}, ]}, /* .... and so on */]

console .log (JSON .stringify (combine (properties), null, 2))

.as-console-wrapper {max-height: 100% !important; top: 0}

但我发现您的输出格式非常重复。我更喜欢这样的东西：

[
  {Size: "S", Color: "Red", Weight: "1kg"},
  {Size: "S", Color: "Red", Weight: "2kg"},
  {Size: "S", Color: "Red", Weight: "3kg"},
  {Size: "S", Color: "Red", Weight: "4kg"},
  {Size: "S", Color: "White", Weight: "1kg"},
  // ...
  {Size: "L", Color: "Blue", Weight: "4kg"},
]

我们可以通过更多的工作来实现它：

const cartesian = ([xs, ...xss]) =>
  xs == undefined
    ? [[]]
  : xs .flatMap (x => cartesian (xss) .map (ys => [x, ...ys]))


const combine = (properties) =>
  cartesian (properties .map (
    ({name, options}) => options .map (({value}) => ({[name]: value}))
  )) .map (ps => Object .assign ({}, ...ps))

const properties = [{name: "Size", options: [ { value: "S" }, { value: "M" }, { value: "L" }, /*...and so on */]}, {name: "Color", options: [ { value: "Red" }, { value: "White" }, { value: "Blue" }, /*...and so on */]}, {name: "Weight", options: [ { value: "1kg" }, { value: "2kg" }, { value: "3kg" }, { value: "4kg"}, ]}, /* .... and so on */]

console .log (combine (properties))

.as-console-wrapper {max-height: 100% !important; top: 0}

如果那个版本的笛卡尔积对你来说没有意义，这个是替代方案：

const cartesian = ([x, ...xs]) => 
  (xs || []) .reduce (
    (a, b) => a .reduce (
      (c, d) => [... c, ... (b .map (e => [... d, e]))],
      []
    ),
    (x || []) .map (x => [x])
  )

Answer 2

这只是对@Scott 已经很棒的回答的补充。我想为 cartesian -

提供两种选择

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

使用 Scott 的 combine 函数 -

for (const c of combine(properties))
  console.log(c)

{"Size":"S","Color":"Red","Weight":"1kg"}
{"Size":"S","Color":"Red","Weight":"2kg"}
{"Size":"S","Color":"Red","Weight":"3kg"}
{"Size":"S","Color":"Red","Weight":"4kg"}
{"Size":"S","Color":"White","Weight":"1kg"}
{"Size":"S","Color":"White","Weight":"2kg"}
{"Size":"S","Color":"White","Weight":"3kg"}
{"Size":"S","Color":"White","Weight":"4kg"}
{"Size":"S","Color":"Blue","Weight":"1kg"}
{"Size":"S","Color":"Blue","Weight":"2kg"}
{"Size":"S","Color":"Blue","Weight":"3kg"}
{"Size":"S","Color":"Blue","Weight":"4kg"}
{"Size":"M","Color":"Red","Weight":"1kg"}
{"Size":"M","Color":"Red","Weight":"2kg"}
{"Size":"M","Color":"Red","Weight":"3kg"}
{"Size":"M","Color":"Red","Weight":"4kg"}
{"Size":"M","Color":"White","Weight":"1kg"}
{"Size":"M","Color":"White","Weight":"2kg"}
{"Size":"M","Color":"White","Weight":"3kg"}
{"Size":"M","Color":"White","Weight":"4kg"}
{"Size":"M","Color":"Blue","Weight":"1kg"}
{"Size":"M","Color":"Blue","Weight":"2kg"}
{"Size":"M","Color":"Blue","Weight":"3kg"}
{"Size":"M","Color":"Blue","Weight":"4kg"}
{"Size":"L","Color":"Red","Weight":"1kg"}
{"Size":"L","Color":"Red","Weight":"2kg"}
{"Size":"L","Color":"Red","Weight":"3kg"}
{"Size":"L","Color":"Red","Weight":"4kg"}
{"Size":"L","Color":"White","Weight":"1kg"}
{"Size":"L","Color":"White","Weight":"2kg"}
{"Size":"L","Color":"White","Weight":"3kg"}
{"Size":"L","Color":"White","Weight":"4kg"}
{"Size":"L","Color":"Blue","Weight":"1kg"}
{"Size":"L","Color":"Blue","Weight":"2kg"}
{"Size":"L","Color":"Blue","Weight":"3kg"}
{"Size":"L","Color":"Blue","Weight":"4kg"}

cartesian 的另一种方法可能如下所示。生成器总是非常适合涉及组合和排列的问题 -

function* cartesian([t, ...more]) {
  if (t == null)
    return yield []
  for (const v of t)
    for (const c of cartesian(more))
      yield [v, ...c]
}

function* combine(t) {
  for (const ps of cartesian(t.map(({name, options}) => options.map(({value}) => ({[name]: value})))))
    yield Object.assign({}, ...ps)
}

for (const c of combine(properties))
  console.log(c)

输出相同 -

{"Size":"S","Color":"Red","Weight":"1kg"}
{"Size":"S","Color":"Red","Weight":"2kg"}
{"Size":"S","Color":"Red","Weight":"3kg"}
...
{"Size":"L","Color":"Blue","Weight":"2kg"}
{"Size":"L","Color":"Blue","Weight":"3kg"}
{"Size":"L","Color":"Blue","Weight":"4kg"}

如果您想将结果收集到数组中，请使用 Array.from。

如何在 Javascript 中生成来自多个对象的项目的所有组合

How to generate in Javascript all combinations of items from multiple objects

javascript

arrays

recursion

combinations

cartesian-product