Compute all permutations of a string in Python

The Problem

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:

  1. Iterate through the initial string – e.g., ‘abc’.
  2. 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 'ac'.
  3. 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 'bac' and 'bca', each of which we’d add to our final results.
  4. 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]
    else:
        for i, c in enumerate(rest):
            s = rest[:i] + rest[i+1:]
            for perm in permute1(c, s):
                res += [start + perm]
    return res

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 start is 'b' and rest is '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:

def permute2(s):
    res = []
    if len(s) == 1:
        res = [s]
    else:
        for i, c in enumerate(s):
            for perm in permute2(s[:i] + s[i+1:]):
                res += 

    return res

When you run this, you get the following:

>>> permute2('abc')
['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.

Bonus

For the masochists, here’s a condensed version using the ternary operator and list comprehensions:

def permute3(s):
    return [s] if len(s) == 1 else +s[i+1:])]

Don’t use this.

Django and PEP 8

If you’re looking around the source for Django, and you’re wondering why arguments that might be named ‘class’ are named ‘klass’ instead of ‘cls’ or ‘class_’ per PEP 8 guidelines (e.g. here), you might be interested to know that the recommendation against ‘klass’ didn’t fully appear in PEP 8 until December, 2005. Prior to that, its use was discouraged, but the major recommendation was consistency.

Hiatus

Between a busy summer trying to finish something up before students return and a side project, I’ve managed to draft 4 long-ish posts and actually publish none of them. So let me say for the record I’m on hiatus here, and hopefully as the year progresses I’ll be able to talk more about some interesting stuff I’m working on.

New domain and platform

After a lot of wrangling, I’ve finally given up on building my own blogging app based on James Bennett‘s coltrane and installed WordPress here at jeremy-boyd.com. There are three main reasons for this. The first is that I don’t have time to make coltrane a valid option for myself. Some features I’d like, such as easy Trackbacks, simply aren’t there. I’m sure coltrane is good for Bennett, but it’s less so for me.

The second reason is that WordPress is a popular platform, and I need to learn how to use it. I have one informal “support contract” for my dad’s company, and a number of people where I work are beginning to use WP as a CMS platform.

The third reason, related to the first, is that I’ve spent a lot of time writing about technology and programming on Facebook lately, and frankly, that’s just not the right platform for that kind of public thought and writing. I’m hoping that switching to WP will let me use the right tools for the job.

In all, I’m looking forward to getting used to the new platform.