How does this complex recursive code work?

Question

I am trying to understand this recursion. I know how recursion works in factorial function but when it gets to this complex recursion like this I am confused. The most confusing part to me is this code

str.split('').map( (char, i) => 
    permutations( str.substr(0, i) + str.substr(i + 1) )map( p => char + p))

First, with "abc", say, it will split into ["a","b","c"] and go through the map function, then go through the second map function to wrap each return with a, b, c, respectively. However, I am very confused at the recursion part.

I thought the first recursion in "a" with value of str as "abc" will return "bc", and second recursion with str value of "bc" will return "c", and so on.

But when I just ran this code to see a clear recursion, it returns

[ [ [ 'c' ], [ 'b' ] ], [ [ 'c' ], [ 'a' ] ], [ [ 'b' ], [ 'a' ] ] ]

This is most confusing to me. I just can't see how this recursion returns these values. Can anyone go more in detail through how this work, like illustrating your thought process step by step?

I am a visual learner. Thank you for your help.

function permutations(str) {
 return (str.length <= 1) ? [str] :
      // Array.from(new Set(
        str.split('')
              .map( (char, i) => 
                     permutations( str.substr(0, i) + str.substr(i + 1))
                           .map( p => char + p))
            //  .reduce( (r, x) => r.concat(x), [])
        //  ));
}

permutations('abc')

Answer 1

One way I prefer to analyze and create recursive solutions is to work as though it's mathematical induction¹.

The trick is to show that the function returns the right value for our base case(s), and then show that if it returns the right value for our simpler cases, it will also return the right value for our current case. Then we know that it will work for all values, as long as each recursive call is to some simpler case that eventually leads to a base case.

So look at your function. I've reformatted it to make discussion easier, and I've restored the reduce call you've commented out. That turns out to be necessary to do this right (although we'll discuss a more modern alternative below.) You also commented out the Array .from (new Set( ... )) wrapper, which is used to remove duplicates in the case your string has repeated characters. Without this, "aba" returns ["aba", "aab", "baa", "baa", "aab", "aba"]. With it, we get ["aba", "aab", "baa"], which makes more sense. But that is separate from our recursion question.

The cleaned-up function looks like this:

function permutations (str) {
  return (str .length <= 1) 
    ? [str] 
    : str 
        .split ('')
        .map ((char, i) => 
          permutations (str .substr (0, i) + str.substr (i + 1))
            .map (p => char + p)
        ) 
        .reduce ((r, x) => r .concat (x), [])
}

permutations('abc')

Our base cases are pretty simple, str.length <= 1. In that case we yield [str]. This only has two possibilities: the string is empty, and we return [''], or the string has a single character, say 'x', and we return ['x']. These are pretty clearly correct, so we move on to the recursive call.

Let's say we pass 'abc'. The split and map calls turn that into the equivalent of this:

[
  permutations ('bc') .map (p => 'a' + p), 
  permutations ('ac') .map (p => 'b' + p),
  permutations ('ab') .map (p => 'c' + p),
]

But we have made the assumption that our recursion works on the smaller strings of 'bc', 'ac', and 'ab'. That means that permutations('bc') will yield ['bc', 'cb'], and similarly for the others, so this is equivalent to

[
  ['bc', 'cb'] .map (p => 'a' + p), 
  ['ac', 'ca'] .map (p => 'b' + p),
  ['ab', 'ba'] .map (p => 'c' + p),
]

which is

[
  ['abc', 'acb']
  ['bac', 'bca']
  ['cab', 'cba']
]

Now we do the reduce call, which successively concatenates each array onto the previous result, starting with [], to get

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

There is a cleaner way of doing this. We can replace the map call followed by this reduce call with a single flatMap call, like this:

function permutations (str) {
  return (str .length <= 1) 
    ? [str] 
    : str 
        .split ('')
        .flatMap ((char, i) => 
          permutations (str .substr (0, i) + str.substr (i + 1))
            .map (p => char + p)
        ) 
}

In any case, we've demonstrated our inductive trick. By assuming this works for the simpler cases, we show that it works for out current case. (And no, we haven't done this rigorously, only by example, but it wouldn't be terribly difficult to prove this with some sort of mathematical rigor.) When we combine that with the demonstration that it works for the base case, we show that it works for all cases. This depends on our recursive calls being simpler in some way that eventually leads to a base case. Here, the strings being passed to the recursive call are one character shorter than those we were supplied, so we know that eventually we will hit our str .length <= 1 condition. And thus we know that it works.

If you add the Array .from (new Set ( ... )) wrapper back on, this will also work for those cases with repeating characters.

---

¹ You may or may not have run across induction, and you may or may not remember it if you did, but in essence, it's very simple. Here's a very simple mathematical induction argument:

We will prove that 1 + 2 + 3 + ... + n == n * (n + 1) / 2, for all positive integers, n.

First, we can easily see that it's true when n is 1: 1 = 1 * (1 + 1) / 2

Next we assume that the statement is true for all integers below n.

We show that it's true for n like this:

1 + 2 + 3 + ... + n is the same as 1 + 2 + 3 + ... + (n - 1) + n, which is (1 + 2 + 3 + ... (n - 1)) + n. But we know that the statement is true for n - 1 (since we assumed it's true for all integers below n), so 1 + 2 + 3 + ... + (n - 1) is, by substituting in n - 1 for n in the expression above, equal to (n - 1) * ((n - 1) + 1) / 2, which simplifies to (n - 1) * n / 2. So now our larger expression ((1 + 2 + 3 + ... (n - 1)) + n is the same as ((n - 1) * n / 2) + n, which we can simplify to (n^2 - n) / 2 + n and then to (n^2 - n + (2 * n)) / 2 and to (n^2 + n) / 2. which factors into n * (n + 1) / 2.

So, by assuming it's true for everything less than n we show that it's true for n as well. Together with the fact that it's true when n is 1, the principle of induction says that it's true for all positive integers n.

You may have seen induction stated slightly differently: If (a) it's true for 1 and (b) being true for n - 1 implies that it's true for n, then (c) it's true for all positive integers n. (The difference here is that we don't need the assumption that it's true for all integers below n, only for n - 1.) It's easy to prove the equivalence of these two models. And the everything below formulation usually makes for a more convenient analogy in recursive problems.

Answer 2

Let's examine permutations('abc').

'abc' is converted to ['a','b','c'] for mapping

Map

a

First, char='a',i=0. Note that permutations(str.substr(0, i) + str.substr(i + 1)) means "get the permutations of all the characters EXCEPT the one I'm looking at. In this case, this means permutations('bc'). Let's assume this gives the correct outputs ['bc','cb'], as the inductive hypothesis.

.map(p => char + p) then tells us to prepend the character we are looking at ('a') to each of the smaller permutations. This yields ['abc',acb'].

b

Following the same logic, char='b',i=1'. permutations('ac') == ['ac','ca']. Final outputs are ['bac','bca']

c

Following the same logic, char='c',i=2'. permutations('ab') == ['ab','ba']. Final outputs are ['cab','cba'].

Thus the overall output of the function would be [['abc','acb'],['bac','bca'],['cab','cba']]...

Answer 3

This is actually a pretty unusual definition of permutations, one that I happen to never have seen before.

(well, as it turns out, I actually wrote an answer once with its near exact equivalent, and only a few years prior... oh my).

In pseudocode, the simply-recursive definition one usually sees is

perms [x, ...xs] = [ [...as, x, ...bs] | p <- perms xs, (as, bs) <- splits p]

but this one is

perms2 xs = [ [x, ...p] | (as, [x, ...bs]) <- splits xs, p <- perms2 [...as, ...bs]]

(with list comprehensions and patterns; sans the empty list cases; with the "natural" definition of splits which builds a list of all possibilities of breaking a list up into two parts).

There's a certain duality here... Interesting. And not "simply"-recursive. :)

Or, with some more named functions to be implemented in obvious ways,

perms [x, ...rest] = [ i | p <- perms rest, i <- inserts x p]
                   = flatMap (inserts x) (perms rest)

--- and this version, 
perms2 xs = [ [x, ...p] | (x, rest) <- picks xs, p <- perms2 rest]

See also:

• Understanding Peter Norvig's permutation solution in PAIP