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]

Answer 2

I've delimited it a bit in order to add some console logs to debug it

This can help of course. However keep in mind that simple recursive definitions can often result in complex execution traces.

That is in fact one of reasons why recursion can be so useful. Because some algorithms that have complicated iterations, admit a simple recursive description. So your goal in understanding a recursive algorithm should be to figure out the inductive (not iterative) reasoning in its definition.

Lets forget about javascript and focus on the algorithm. Let's see we can obtain the permutations of elements of a set A, which we will denote P(A).

Note: It's of no relevance that in the original algorithm the input is a list, since the original order does not matter at all. Likewise it's of no relevance that we will return a set of lists rather than a list of lists, since we don't care the order in which solutions are calculated.

Base Case:

The simplest case is the empty set. There is exactly one solution for the permutations of 0 elements, and that solution is the empty sequence []. So,

P(A) = {[]}

Recursive Case:

In order to use recursion, you want to describe how to obtain P(A) from P(A') for some A' smaller than A in size.

Note: If you do that, it's finished. Operationally the program will work out via successive calls to P with smaller and smaller arguments until it reaches the base case, and then it will come back bulding longer results from shorter ones.

So here is one way to write a particular permutation of an A with n+1 elems. You need to successively pick one element of A for each position:

 _   _ ... _ 
n+1  n     1

So you pick an x ∈ A for the first

 x   _ ... _ 
     n     1

And then you need to choose a permutation in P(A\{x}).

This tells you one way to build all permutations of size n. Consider all possible choices of x in A (to use as first element), and for each choice put x in front of each solution of P(A\{x}). Finally take the union of all solutions you found for each choice of x.

Let's use the dot operator to represent putting x in front of a sequence s, and the diamond operator to represent putting x in front of every s ∈ S. That is,

x⋅s = [x, s1, s2, ..., sn] 
x⟡S = {x⋅s : s ∈ S}

Then for a non-empty A

P(A) = ⋃ {x⟡P(A\{x}) : x ∈ A} 

This expression together with the case base give you all the permutations of elements in a set A.

The javascript code

To understand how the code you've shown implements this algortithm you need to consider the following

• That code considers two base cases, when you have 0 or 1 elements, by writing xs.length < 2. We could have done that too, it's irrelevant. You can change that 2 into a 1 and it should still work.

• The mapping corresponds to our operation x⟡S = {x⋅s : s ∈ S}

• The without corresponds to P(A\{x})

• The flatten corresponds to the ⋃ which joins all solutions.