Here’s a problem I was asked recently:
Write a function permute such that:
permute('abc') → ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Now, immediately this should look like a recursive problem. Put in English, we want to do the following:
- Iterate through the initial string – e.g., ‘abc’.
- For each character in the initial string, set aside that character and get a list of all permutations of the string that’s left. So, for example, if the current iteration is on
'b', we’d want to find all the permutations of the string
- Once you have the list from step 2, add each element from that list to the character from the initial string, and append the result to our list of final results. So if we’re on
'b' and we’ve gotten the list
['ac', 'ca'], we’d add
'b' to those, resulting in
'bca', each of which we’d add to our final results.
- Return the list of final results.
I was asked this in a somewhat high-pressure situation, and although I could come up with this explanation in English, I couldn’t produce the solution as cleanly as I would have liked. I’m writing it up here both to cement my own understanding of the problem and to help people get clear on what really is a fairly basic example of recursion in Python.
A Solution … Sorta
I eventually came up with something like this:
def permute1(start, rest):
res = 
if len(rest) <= 1:
res += [start + rest, rest + start]
for i, c in enumerate(rest):
s = rest[:i] + rest[i+1:]
for perm in permute1(c, s):
res += [start + perm]
This code works, after a fashion:
>>> permute('', 'abc')
['abc', 'acb', 'acb', 'abc', 'bac', 'bca', 'bca', 'bac', 'cab', 'cba', 'cba', 'cab']
But it’s embarrassing. For one thing, it produces duplicates in our list, which is obviously not what we want. For another, it takes two arguments, not one. In other words, it doesn’t solve the problem.
My initial inclination to solve the first problem was to use Python’s built-in set datatype. This was overkill, as it turns out. The duplicates are being caused by the line
res += [start + rest, rest + start]. Imagine if
'c'. Then the algorithm will, in the base case, add
['bc', 'cb'] to
res before passing it back. This is just unnecessary, since our for loop below will catch the
'cb' case later on. So a quick fix to that line, adding just
[start + rest], will fix the first issue.
However, a correct solution would only take one argument, so we’re still not quite there.
Don’t Overthink Recursion
The problem really is that I was overthinking it. Here’s a trick when it comes to solving recursive problems: just write your function as though when you call it recursively it’ll work as expected. In the English explanation above I had a bit about getting a list of all the permutations of the remaining string. Obviously, that’s exactly the same problem as getting a list of all permutations of the original string! So I just needed to hammer out the problem and not get ahead of myself.
When I sat down to just type, here’s what came out:
res = 
if len(s) == 1:
res = [s]
for i, c in enumerate(s):
for perm in permute2(s[:i] + s[i+1:]):
res += [c + perm]
When you run this, you get the following:
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Much nicer! Not only does it work as expected, but the code feels cleaner than before. Also note that, in both examples, I use Python’s built-in enumerate() to avoid the fairly un-Pythonic tricks using
range(len(s)) you see in places like this.
For the masochists, here’s a condensed version using the ternary operator and list comprehensions:
return [s] if len(s) == 1 else [c + perm for i, c in enumerate(s) for perm in permute3(s[:i]+s[i+1:])]
Don’t use this.