Javascript array recursion question – looping through “sections”

I’m strugguling with Javascript on how to find all combinations of an array source with n depth that is broken into sections (0, 1, & 2 in example below). I want to end up with each possible cominbation – and each returned array should include one and only one value from each group. I’ve hardcoded a solution to 4 levels, but need more flexibility – the flexibility that recursion provides. I’ve reviewed lots of possible recursive solutions, and while I understand how those work I just can’t figure out how to get this particular source data to work.

sourceArr=[
     [0,60,100]
    ,[0,60,200]
    ,[0,66,300]
    ,[1,69,500]
    ,[2,70,600]
    ,[2,70,700]
    ,[2,77,800]
    ,[2,77,900]
]

Intended return value…

[
    [{60,100],{69,500},{70,600}]
    ,[{60,100],{69,500},{70,700}]
    ,[{60,100],{69,500},{77,800}]
    ,[{60,100],{69,500},{77,900}]
    ,[{60,200],{69,500},{70,600}]
    ,[{60,200],{69,500},{70,700}]
    ,[{60,200],{69,500},{77,800}]
    ,[{60,200],{69,500},{77,900}]
    ,[{66,300],{69,500},{70,600}]
    ,[{66,300],{69,500},{70,700}]
    ,[{66,300],{69,500},{77,800}]
    ,[{66,300],{69,500},{77,900}]
]

Answer

In essence, this is a cartesian product question. But you have to get to it first, as you don’t have the elements you want to group in separate arrays. So first, you need to group the arrays by their first element and strip that first element off.

If we use a number of simple utility functions, we can write a straightforward version like this:

const combine = pipe (
  group (head),
  map (map (tail)),
  cartesian
) 

Here we pipe together a number of functions, creating a new function which takes some input, sends that to the first function, and then sending the output of that one to the second, and the output of that to the third, and so on, returning the final output.

The first function we supply in this pipeline groups the elements supplied into arrays based on the result of the head function applied to each (which simply returns the first element of an array.) That will leave us with a structure like this:

[
  [[0, 60, 100], [0, 60, 200], [0, 66, 300],
  [[1, 69, 500]],
  [[2, 70, 600], [2, 70, 700], [2, 77, 800], [2, 77, 900]]
]

Next we use a nested map call, passing tail to the innermost one. tail simply returns everything but the first element of an array. That will convert the above to

[
  [[60, 100], [60, 200], [66, 300],
  [[69, 500]],
  [[70, 600], [70, 700], [77, 800], [77, 900]]
]

And this is now in a format to be used by a Cartesian product function, so we include a simple cartesian function and we’re done.

We can write those helpers like this:

// utility functions
const head = (xs) => xs [0]
const tail = (xs) => xs .slice (1)
const map = (fn) => (xs) =>
  xs .map (x => fn (x))
const pipe = (...fns) => (x) =>
  fns .reduce ((a, fn) => fn (a), x)
const group = (fn) => (xs) =>
  Object .values (xs .reduce (
    (a, x, _, __, k = fn (x)) => ((a[k] = [...(a[k] || []), x]), a), 
    {}
  ))
const cartesian = ([xs, ...xss]) =>
  xs == undefined
    ? [[]]
  : xs .flatMap (x => cartesian (xss) .map (ys => [x, ...ys]))

// main function
const combine = pipe (
  group (head),
  map (map (tail)),
  cartesian
) 

// sample data
const sourceArr = [[0, 60, 100], [0, 60, 200], [0, 66, 300], [1, 69, 500], [2, 70, 600], [2, 70, 700], [2, 77, 800], [2, 77, 900]]

// demo  -- stringify is to avoid SO's id-ref presentation
console .log (JSON.stringify(combine (sourceArr), null, 4))

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

Note that in order to do this, I used functions I have lying around. It took far longer to write this answer than it did to come up with the code. That’s the advantage of maintaining a library of reusable functions you can grab as you need.

These specific APIs are similar to Ramda‘s design. That’s no surprise, as I’m a Ramda founder and maintainer, but they are simple to create and maintain on our own.