understanding better a solution for finding permutations of a string - javascript

Question

I'm trying to get a better understanding of recursion as well as functional programming, I thought a good practice example for that would be to create permutations of a string with recursion and modern methods like reduce, filter and map.

I found this beautiful piece of code

const flatten = xs =>
    xs.reduce((cum, next) => [...cum, ...next], []);

const without = (xs, x) =>
    xs.filter(y => y !== x);

const permutations = xs =>
    flatten(xs.map(x =>
        xs.length < 2
            ? [xs]
            : permutations(without(xs, x)).map(perm => [x, ...perm])
    ));
    
permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

from Permutations in JavaScript? by Márton Sári

I've delimited it a bit in order to add some console logs to debug it and understand what's it doing behind the scenes

const flatten = xs => {
  console.log(`input for flatten(${xs})`);
  return xs.reduce((cum, next) => {
    let res = [...cum, ...next];
    console.log(`output from flatten(): ${res}`);
    return res;
  }, []);
}

const without = (xs, x) => {
  console.log(`input for without(${xs},${x})`)
  let res = xs.filter(y => y !== x);
  console.log(`output from without: ${res}`);
  return res;
}

const permutations = xs => {
  console.log(`input for permutations(${xs})`);
  let res = flatten(xs.map(x => {
    if (xs.length < 2) {
      return [xs]
    } else {
      return permutations(without(xs, x)).map(perm => [x, ...perm])
    }
  }));
  console.log(`output for permutations: ${res}`)
  return res;
}

permutations([1,2,3])

I think I have a good enough idea of what each method iss doing, but I just can't seem to conceptualize how it all comes together to create [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

can somebody show me step by step what's going on under the hood?

Answer 1

To get all permuations we do the following:

We take one element of the array from left to right.

 xs.map(x => // 1

For all the other elements we generate permutations recursively:

 permutations(without(xs, x)) // [[2, 3], [3, 2]]

for every permutation we add the value we've taken out back at the beginning:

 .map(perm => [xs, ...perm]) // [[1, 2, 3], [1, 3, 2]]

now that is repeated for all the arrays elements and it results in:

 [
  // 1
  [[1, 2, 3], [1, 3, 2]],
  // 2
  [[2, 1, 3], [2, 3, 1]],
  // 3
  [[3, 1, 2], [3, 2, 1]]
]

now we just have to flatten(...) that array to get the desired result.

The whole thing could be expressed as a tree of recursive calls:

 [1, 2, 3]
        - [2, 3] -> 
                   - [3] -> [1, 2, 3]
                   - [2] -> [1, 3, 2]
        - [1, 3] ->
                  - [1] -> [2, 3, 1]
                  - [3] -> [2, 1, 3]
        - [1, 2] -> 
                 - [1] -> [3, 2, 1]
                 - [2] -> [3, 1, 2]