Javascript array recursion question - looping through "sections"

Question

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

I don't understand the logical relation between `sourceArr` and the expected output — Jeremy Thille, Dec 01 '21 at 19:41
It would be good if you include your code also, even if it didn't work. — Marcel Kohls, Dec 01 '21 at 20:19
why do you need a recursion? had you have a look [here](https://stackoverflow.com/questions/4331092/finding-all-combinations-cartesian-product-of-javascript-array-values) or [here](https://stackoverflow.com/questions/12303989/cartesian-product-of-multiple-arrays-in-javascript)? — Nina Scholz, Dec 01 '21 at 20:55
@NinaScholz: you don't need it, but recursion is one useful way to write a cartesian product function. Also note that for instance, [your generally useful answer](https://stackoverflow.com/a/52310125) in the first link may not work, as it would do an unwanted level of flattening. — Scott Sauyet, Dec 01 '21 at 21:38

score 0 · Accepted Answer · answered Dec 01 '21 at 21:30

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.

Thanks so much! I needed to JSON.parse it to get it back to an array and then will need to move each child array element into a single element, but this is great! — brian123, Dec 01 '21 at 21:43
I forgot to mention that your expected output is not well-formatted, mixing brace styles oddly. But the result of my `combine` is not a string. The call to `JSON.stringify` is only there for cleaner reporting in the StackOverflow console. It's actually an array, one that looks like `[[[60, 100], [69, 500], [70, 600]], [[60, 100], [69, 500], [70, 700]], [[60, 100], [69, 500], [77, 800]], ..., [[66, 300], [69, 500], [77, 900]]]`. — Scott Sauyet, Dec 01 '21 at 21:49

Javascript array recursion question - looping through "sections"

1 Answers1