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:

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.

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.

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.

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\).

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 `set`

s instead of `str`

s!