Find all path combinations

Question

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.

Answer 1

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.

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]]
 // [[]]

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).

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]]
 // [[]]