Question 202187 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – 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.

Tags:

2

Answers


  1. 0

    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);
    Login or Signup to reply.
  2. 0

    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.

    const flatPath = function*(array, prefix = []) {
  const next = array[0];
  if (!next) { // 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 ]
]
*/
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search