Infinite Recursive Permutation Generators

Consider the following ten lines of code:

def gen_perms(s, n=1):
    if n < 1:
        yield ''
    for prefix in gen_perms(s, n-1):
        for c in s:
            yield prefix + c
    gen_perms(s, n+1)

for perm in gen_perms('abcdefghijklmnopqrstuvwxyz'):
    print(perm)

In a nutshell, this prints out every possible permutation of letters of the alphabet, in “spreadsheet column name” order (a, b, c…, aa, ab, ac…, aaa, aab, aac…). Every dictionary word. Every great speech. Entire (unpunctuated) works of Shakespeare.

For now, we’ll ignore a few basic improvements. This could easily be generalized to work with more than just strings. The runtime isn’t too great either since we’re doing a bunch of recalculation. Memoization and choosing better data types would fix these, but let’s focus on the aesthetic qualities of this code, and on how it actually works.

Starting with the easy bit. Assume we have an infinite permutation generator called gen_perms that takes a string and gives back all the possible permutations of that string based on the order the characters were passed in. In that case, this loop will run through those infinite permutations and print out each one:

for perm in gen_perms('abcdefghijklmnopqrstuvwxyz'):
    print(perm)

Let’s get into the real meat of it though. gen_perms takes a string s, and a parameter n. You can think of n as the length of the permutations currently being generated.

def gen_perms(s, n=1):

The body of the function has three parts. First of all, if n is less than one, we want to give back an empty string. This is our recursive base case, and should be pretty straightforward.

    if n < 1:
        yield ''

Glossing over the tricky middle bit for a second, here’s the third part of the function body. Just like we need a base case for termination, if we want infinite generation we need an ever-growing case. Here, we just call gen_perms with the next largest permutation length so it can compute all of those for us. This will keep growing as n reaches ever higher towards infinity.

    gen_perms(s, n+1)

Here’s the fun stuff. First, we inductively assume that gen_perms works for n-1. That should generate all the permutations of length \(n-1\) for us, and we’ll iterate over each of them as prefix. Because a prefix is of length \(n-1\), and we want to generate a permutation of length \(n\), all we need to do is add a single character to prefix. These single characters have an obvious source: each character in s, in order. Eventually, with all the possible prefixes having all the possible characters in s appended to them, we manage to come up with all the possible permutations of length \(n\).

    for prefix in gen_perms(s, n-1):
        for c in s:
            yield prefix + c

This code manages to combine several fairly tricky topics—recursion, infinity, permutations, generators—into one short sample, which I think makes it a super fun example to work with. For bonus points, try writing the memoized version, or a version that works with sets instead of strs!