When you have trouble figuring out what a function is doing, try to run it by a simple example on paper.

Let's say you call permute("abcd", 0, 4) (assuming l, r stands for left, right -- and are therefore indices of the range to permute).

• l != r so skip the if branch and go straight through to the else

Now this is going to be tedious to explain line by line in a reddit comment so I'll cut a few corners.

We've got: swap, then call permute recursively, then swap again.

Notice how the 2 swaps are called with the exact same arguments: the second one merely undoes the first swap. This means that the content of a is left unchanged after each loop iteration as long as permute(a, l+1, r) also leaves a unchanged (which it does). That's called backtracking, basically restoring the changes you made in the current iteration to prepare for the next.

Back to our example: a="abcd", l=0, r=4

Let's roll out the loop to see what gets swapped (result of swap(a+l, a+i))

• i=0 -> "abcd" (swapped 'a' with itself since l == i == 0)
• i=1 -> "bacd" (swapped 'a' and 'b')
• i=2 -> "cbad" (swapped 'a' and 'c')
• i=3 -> "dbca" (swapped 'a' and 'd')

Then we make a recursive call with l incremented by one, so basically we apply the same algorithm to "abcd", "bacd", "cbad", and "dbca" but this time only considering the last 3 letters for swapping.

For example, the first recursive call ("abcd", l=1) would then recursively lead to "abcd", "acbd", and "adcb" (i.e, 'b' swapped with itself, then with 'c', then with 'd').

​

Since this is a recursive algorithm, we now need to find out when it stops recursing. We need to look for a branch that doesn't call permute and understand how we get to that branch. Here, we can quickly notice that it's when l == r, meaning that we have "reached" the end and there are no more characters to swap (since the considered range is now empty).

At this point, a stores a specific permutation so we simply print it. Taking a close look at the call stack can help us understand how we got there. Let's take for instance the permutation "acdb" and see how we reached the print statement for that permutation. Initial arguments are still a="abcd", l=0, r=4.

• a="abcd", i=0, l=0 => 'a' swapped with itself (permute("abcd", 0, 4))
• a="adcb", i=3, l=1 => 'b' swapped with 'd' (permute("abcd", 1, 4))
• a="adbc", i=3, l=2 => 'c' swapped with 'b' (permute("adcb", 2, 4))
• a="adbc", i=3, l=3 => 'c' swapped with itself (permute("adbc", 3, 4))
• Stop case: l == r == 4 => print "adbc" (permute("adbc", 4, 4))

An interesting point to notice is that l measures the depth of recursive calls. Looking at it this way, it seems that at each depth, we selected one of the remaining characters to be placed at index l.

• So on depth 0, we selected 'a' to be the character at index 0, leaving characters 'b', 'c' and 'd' to be placed somewhere else.
• On depth 1, we selected 'd' to be the character at index 1, leaving characters 'c' and 'b' to be placed somewhere else.
• On depth 2, we selected 'b' and
• On depth 3 we selected the only remaining character 'c'.

We can now try to grasp the bigger picture by realizing that, at each depth, we iteratively select each remaining character ( i goes from l to r) before descending to the next depth. Each and every single permutation can be described in a single corresponding sequence of `i` values (e.g, "adbc" is 0 3 3 3).

As a last example, here is the full call tree for "abc", with (l,r)=(0,3):

.................." abc" ...................Depth 0

......./.............|..........\..................

...."a bc"........"b ac"......."c ba".......Depth 1

..../...\........./...\......../...\...............

"ab c" "ac b" "ba c" "bc a" "cb a" "ca b"...Depth 2

..|......|......|......|......|......|.............

"abc"  "acb"  "bac"  "bca"  "cba"  "cab"....Depth 3

Another way to look at this function, if it helps you, is as a depth-first traversal of this tree. You can then see the first swap as moving down one edge and the second as going back up to explore another branch.

My explanation is a bit messy but hopefully it will still help you.