Find all path combinations

Don't know if this has a specific name, but I need to flatten an array of 1D arrays and simple elements, in a way that all combinations untill a leaf "node" are reported. Here's an example because the above leaves a lot to the imagination:

// My input array contains single elements or 1D arrays:
let input = [1, 2, [3, 4], [5, 6]];

The unfolding proceeds so that each time an array is encountered, the paths are split into as many elements as the array contains:

// current result = [1, 2]
// unconsumed input [[3, 4], [5, 6]]
// ->
// current result = [ [1, 2, 3], [1, 2, 4] ]

// current result = [ [1, 2, 3], [1, 2, 4] ]
// unconsumed input [[5, 6]]
// ->
// final result = [ [1, 2, 3, 5], [1, 2, 4, 5], [1, 2, 3, 6], [1, 2, 4, 6] ]

I may be messing something up with copies and aliasing but can't seem to make it work right and handle special cases like:

let input1 = [1, 2, 3]; // No nested arrays
let input2 = [];        // Empty input

Tried building the result backwards since .pop is convenient to use here but can't get it to work:

function flatPath(input, result = [[]]) {
    while (input.length) {
        const last = input.pop();

        if (Array.isArray(last)) {
            result = flatPath(last, [...result, ...result]);
        } else {
            for (let ar of result) {
                result.push(last);
            }
        }
    }
    return result;
}

let result = flatPath([1, 2, [3, 4], [2, 5, 6] ]);

console.log(result);

but can't even get past compilation (I'm using typescript) since all I get is:

> Parameter 'input' implicitly has an 'any' type.

> Argument of type 'any' is not assignable to parameter of type 'never'.

What is the problem with my code or is there a better (more idiomatic) way to do this.

This is a great use-case for a generator function, because it allows you to yield results at the leave notes (whose cardinality is unknown a-priori), rather having to handle the aggregation back up the calling tree of the recursion.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

const flatPath = function*(array, prefix = []) {
  const next = array[0];
  if (next === undefined) { // base case
    yield prefix;
  } else if (next instanceof Array) {
    for (let item of next) {
      yield * flatPath(array.slice(1), [...prefix, item]);
    }
  } else {
    yield * flatPath(array.slice(1), [...prefix, next]);
  }
};

const result = Array.from(flatPath([1, 2, [3, 4], [2, 5, 6]]));
console.log(result);

/* output:
[
  [ 1, 2, 3, 2 ],
  [ 1, 2, 3, 5 ],
  [ 1, 2, 3, 6 ],
  [ 1, 2, 4, 2 ],
  [ 1, 2, 4, 5 ],
  [ 1, 2, 4, 6 ]
]
*/

<!-- end snippet -->

You can handle this without passing down a context array by aggregating the results from the bottom up here using map() to add each non-array element from the previous call to the returned sub-arrays from deeper calls.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function flatPath([next, ...rest]) {
  if (next === undefined) {
    return [[]];
  }

  if (Array.isArray(next)) {
    const temp = [];
    for (const n of next) {
      temp.push(...flatPath([n, ...rest]));
    }
    return temp;
  }

  return flatPath(rest).map(t => [next, ...[].concat(t)]);
}


// Test output
for (const test of [
  [1, 2, [3, 4], [5, 6]],
  [1, 2, 3], 
  [[1, 2, 3], 4], 
  []
]) {
  let result = flatPath(test);
  console.log(JSON.stringify(result));
}

 // [[1,2,3,5],[1,2,3,6],[1,2,4,5],[1,2,4,6]]
 // [[1,2,3]]
 // [[1,4],[2,4],[3,4]]
 // [[]]

<!-- end snippet -->

The above will fail if you have an undefined element in your array which is fixed below by checking against the ...rest length to determine the bottom (and an explicit check for empty arrays passed as input).

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function flatPath(input) {
  if (input.length === 0) {
    return [];
  }

  const [next, ...rest] = input;

  if (Array.isArray(next)) {
    const temp = [];
    for (const n of next) {
      const tail = rest.length
        ? flatPath([n, ...rest])
        : flatPath([].concat(n));

      temp.push(...tail);
    }
    return temp;
  }

  return rest.length
    ? flatPath(rest).map(t => [next, ...[].concat(t)])
    : [next];
}

// Test output
for (const test of [
  [1, 2, [3, 4], [5, 6]],
  [1, 2, 3], 
  [[1, 2, 3], 4], 
  []
]) {
  let result = flatPath(test);
  console.log(JSON.stringify(result));
}

 // [[1,2,3,5],[1,2,3,6],[1,2,4,5],[1,2,4,6]]
 // [[1,2,3]]
 // [[1,4],[2,4],[3,4]]
 // [[]]

<!-- end snippet -->

I am able to compile your code but it goes into infinite loop. I think the problem is this part;

        for (let ar of result) {
            result.push(last);
        }

You are pushing elements to the result array while iterating over it. This causes an infinite loop.

To fix this issue, you can create a separate array to store the new elements and then concatenate it with the result array outside the loop.

The following works fine;

        const newElements = [];
        for (let ar of result) {
            newElements.push(last);
        }
        result = result.concat(newElements);

This version, written independently, expresses the same algorithm as the answer from pilchard. But it cleans some things up and uses pure expressions rather than statements, as I always prefer:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

const process = ([xs, ...xss], rs = xs !== undefined && process(xss)) =>
  xs === undefined
    ? [[]]
  : Array.isArray(xs)
    ? xs.flatMap(x => rs.map(r => [x, ...r]))
  : rs.map(r => [xs, ...r]);

const input = [1, 2, [3, 4], [5, 6]]

console .log(JSON.stringify(process (input)))

<!-- end snippet -->

Pilchard's answer also expressed concern over possibly undefined values in the input. If that is a concern, an easy solution would be to introduce a Symbol, like this:

const None = Symbol()

const process = ([xs = None, ...xss], rs = xs !== None && process(xss)) =>
  xs === None
    ? [[]]
  : Array.isArray(xs)
    ? xs.flatMap(x => rs.map(r => [x, ...r]))
  : rs.map(r => [xs, ...r])

const input = [1, 2, [3, 4], [5, 6]]

But I wouldn't bother unless you expect -- and want to handle -- undefined values.