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 +1) gen_perms(s, n 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
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.
takes a string
s, and a parameter
n. You can
n as the length of the permutations currently
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
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
n reaches ever higher towards infinity.
+1) gen_perms(s, n
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
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
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