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

Question

I have an array of objects with names and options and I need all possible combinations of products. The important part is that this array has an N number of objects with N number of options in every object.

I tried to create some kind of recursive algorithm, but the problem is that I failed to push recursively to receive the needed data structure in the end. I also tried the approach from Cartesian product of multiple arrays in JavaScript but it seems it is not relevant to the output needed.

Example:

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

I need to have all the possible combinations in the form of the array which itself includes an array of objects with the object's name and value.

Example (Array of arrays):

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

Does this answer your question? [Cartesian product of multiple arrays in JavaScript](https://stackoverflow.com/questions/12303989/cartesian-product-of-multiple-arrays-in-javascript) — pilchard, Nov 18 '21 at 15:10
Welcome to [so]! Please take the [tour], visit the [help] and read up on [asking good questions](https://stackoverflow.com/help/asking). After doing some research and [searching](https://stackoverflow.com/help/searching) for related topics on SO, try it yourself. If you're stuck, post a [mcve] of your attempt and note exactly where you're stuck. People will be glad to help. — Scott Sauyet, Nov 18 '21 at 16:16
@pilchard, unfortunately not, I need to implement the solution for an array of objects and I need to preserve both values from the object in the output, as in the example. — mdct, Nov 18 '21 at 16:18
regardless of the contents of the array the method is the same. — pilchard, Nov 18 '21 at 16:35
@pilchard how can the method from [Cartesian product of multiple arrays in JavaScript](https://stackoverflow.com/questions/12303989/cartesian-product-of-multiple-arrays-in-javascript) be implemented in my case? — mdct, Nov 18 '21 at 17:07

Mulan · Answer 1 · 2021-11-19T05:06:31.657

This is only a supplement to @Scott's already terrific answer. I wanted to offer two alternatives for cartesian -

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

Using Scott's combine function -

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"}

Another approach to cartesian might look like this. Generators are always a great fit for problems involving combinations and permutations -

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)

Output is identical -

{"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"}

Use Array.from if you would like to collect the results in an array.

Thank you for your answer! Generators approach also looks really great. — mdct, Nov 19 '21 at 08:59

Scott Sauyet · Accepted Answer · 2021-11-19T15:15:09.140

Update: Fixed the first cartesian implementation based on suggestion from Mulan.

This is definitely a cartesian product question. The only thing is that you will need to format your input before you call the cartesian product. Here is one version, using a simple, recursive cartesian function.

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}

But I find your output format quite repetitive. I would prefer something like:

[
  {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"},
]

and we can achieve it with just a bit more work:

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}

If that version of the cartesian product does not make sense to you, this one is an alternative:

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

Thank you for your answer! This is exactly the solution I was looking for but was stuck on the recursion step. The solution is extremely compact and efficient — mdct, Nov 18 '21 at 18:51
assignment of `xs = undefined` looks like a potential mistake — Mulan, Nov 19 '21 at 04:32
unless i am overlooking something, i think i found a way around the `length` check. i would've included as an edit but unsure if you feel it would clash with your post. supplemental answer provided. — Mulan, Nov 19 '21 at 04:58
@Mulan: Not only is it a typo, but it's an entirely unnecessary check as your own answer shows! I will update, but please, always feel free to edit my answers. — Scott Sauyet, Nov 19 '21 at 14:17

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

2 Answers2