How to group/flatten array into all combinations of sub-arrays

Question

Wondering how to take a nested array such as this:

var arr = [
    1,
    [ 
        2, 3, 4, 
        [ 
            5, 6, 7, 8, 
            [ 9, 10 ], 
            [ 11, 12 ]
        ], 
        [ 13, 14 ] 
    ] 
]

And apply a grouping function:

function group(arr) {

}

Such that it converts arr into the following:

var output = [
  [1, 2, 5, 13, 9, 11],
  [1, 2, 5, 13, 9, 12],
  [1, 2, 5, 13, 10, 11],
  [1, 2, 5, 13, 10, 12]

  [1, 3, 5, 13, 9, 11],
  [1, 3, 5, 13, 9, 12],
  [1, 3, 5, 13, 10, 11],
  [1, 3, 5, 13, 10, 12],

  [1, 3, 6, 13, 9, 11],
  [1, 3, 6, 13, 9, 12],
  [1, 3, 6, 13, 10, 11],
  [1, 3, 6, 13, 10, 12],

  [1, 3, 7, 13, 9, 11],
  [1, 3, 7, 13, 9, 12],
  [1, 3, 7, 13, 10, 11],
  [1, 3, 7, 13, 10, 12],

  ...

  [1, 4, 5, 13, 9, 11],
  [1, 4, 5, 13, 9, 12],
  [1, 4, 5, 13, 10, 11],
  [1, 4, 5, 13, 10, 12],

  ...
]

Basically it flattens the array, or you could say gets every combination of all sub arrays, and returns them in a flat list. Breaking my head on this one.

I'm not sure how to describe better than the example output. — Lance, Jan 30 '18 at 13:01
Building an array with all combinations of subarrays is the best I can do atm. — Lance, Jan 30 '18 at 13:04
why do you have a nested structure, a just on level deep array would work. — Nina Scholz, Jan 30 '18 at 13:05
@LancePollard Your example output seems wrong. Shouldn't `13` be in the last column? — Bergi, Jan 30 '18 at 13:23
Yeah that works, I wasn't even sure what the order should be but that makes more sense. — Lance, Jan 30 '18 at 13:30
The other question is the order of elements. By current example, nested arrays do not get followed by simple value but can this be the case? For example, `var output = [1, [...], 2];` — lolbas, Jan 31 '18 at 04:18

Bergi · Answer 1 · 2018-01-30T13:37:05.300

Looks pretty simple - you want to apply the cartesian product on all of the nesting levels, and recursively flatten the elements.

However, your input is a bit weird, it would have been easier (and more flexible!) if you had used

var arr = [
    [ 1 ],
    [
        [ 2, 3, 4 ],
        [
            [ 5, 6, 7, 8 ],
            [ 9, 10 ],
            [ 11, 12 ]
        ],
        [ 13, 14 ]
    ]
];

So now it requires some slicing to split the two parts of each array:

function flatten(arr) { return [].concat(...arr); }
function group(arr) {
    const i = arr.findIndex(Array.isArray)
    return i < 0
      ? arr
      : cartesian([arr.slice(0, i), ...arr.slice(i).map(group)]).map(flatten);
}

With the flexible input format, it would be just

function group(arr) {
  return arr.every(Array.isArray) // or even Array.isArray(arr[0])?
    ? cartesian(arr.map(group)).map(flatten) // group simply every element - even the first
    : arr;
}

How to group/flatten array into all combinations of sub-arrays

1 Answers1