Generating combinations from multiple Arrays of object

Question

I have array: [{key: 1, value: 1}, {key: 2, value:2}, {key: 3, value: 3}] another array: [[{key: 1, value: 12}, {key: 1, value: 13}], [{key: 2, value: 21}], [{key: 4, value:4}, {key: 5, value: 5}]]

I want to generate resulting array as:

[
[{key: 1, value: 1}, {key: 2, value:2}, {key: 3, value: 3}, {key: 4, value:4}, {key: 5, value: 5}], 
[{key: 1, value: 12}, {key: 2, value:2}, {key: 3, value: 3}, {key: 4, value:4}, {key: 5, value: 5}], 
[{key: 1, value: 13}, {key: 2, value:2}, {key: 3, value: 3}, {key: 4, value:4}, {key: 5, value: 5}], 
[{key: 1, value: 1}, {key: 2, value:21}, {key: 3, value: 3}, {key: 4, value:4}, {key: 5, value: 5}], 
[{key: 1, value: 12}, {key: 2, value:21}, {key: 3, value: 3}, {key: 4, value:4}, {key: 5, value: 5}], 
[{key: 1, value: 13}, {key: 2, value:21}, {key: 3, value: 3}, {key: 4, value:4}, {key: 5, value: 5}]
]

I am able to generate combinations of array2 using reduce + concat.

const array2 = [[{key: 1, value: 12}, {key: 1, value: 13}], [{key: 2, value: 21}], [{key: 4, value:4}], [{key: 5, value: 5}]];

const combinations = array2.reduce((accumulator, current) =>
      accumulator.reduce((objAccumulator, currentObj) =>
        objAccumulator.concat(
          current.map(obj => [].concat(currentObj, obj))), []));
          
console.log(combinations);

but i am not able to find a good/optimized solution to arrive at the final result. Any help would be appreciated.

Yunhai · Accepted Answer · 2020-11-28T03:22:53.067

I try to add my thought into comment but the space is not enough.

Not sure about what constraints you actually have. Probably you can list out all possibility from all arrays and then make all combinations later to reduce the time complexity;

For example, convert all values from input arrays to a map like the following

{
  //I highly suggest use a set here instead of a list so you don't need to 
  //worry about duplicate number while adding new values
  1: [1, 12 ,13],
  2: [2, 21],
  3: [3],
  4: [4],
  5: [5],
}

then you can combine all values from a n arrays, which it's already answer from the past: JavaScript - Generating combinations from n arrays with m elements.

This is the best solution I can imagine theoretically since you only have the extra O(sum of all arrays size) + the combination cost, in which I don't believe there are much space you can reduce.

Generating combinations from multiple Arrays of object

1 Answers1