A few years ago, while in graduate school, I wrote an article on Knuth and Ruskey's use of coroutines for combinatorial generation. The basic idea behind it was to use a set of coroutines that are linked together and have them "poke" each other when needed to generate a set of combinatorial objects. A few days ago I was talking to someone about writing a simple program to generate all permutations of a list and I mentioned that coroutines can be used in such a manner for it. In the aforementioned article, I use the coroutine approach to implement Steinhaus-Johnson-Trotter's permutation generation algorithm, but I figured a much simpler permutation generation algorithm can be created using the same approach as well. To showcase it, I ended up writing the following code and later decided it would make for a good very short post on the blog, and here it is!

The basic idea is to generate all permutations of `pi`

by recursively
generating all sub-permutations of `pi[1:]`

and then shifting `pi[0]`

to the right one at a time. At the end, we undo all the shifts to the right by
doing a cyclic shift to the left.

Of course the algorithm to generate the permutations itself is trivial. What
makes the code a bit different is using coroutines to do the recursion, with
each call to each coroutine yielding `True`

if it generates a new
permutation, and `False`

otherwise. A "nobody" coroutine which always
yields `False`

is used as the base case for an empty list since no new
permutation of the empty list exists. Marking the end of each coroutine's job
by a yielding of `False`

means the same coroutines can go back to work
right after.

```
def permutations(pi, i):
if i == len(pi):
while True:
yield False
sub_permutations = permutations(pi, i + 1)
while True:
# Shift the first element to the right, producing a new permutation for
# each shift.
for j in range(i, len(pi) - 1):
pi[j], pi[j + 1] = pi[j + 1], pi[j]
yield True
# Do a cyclic shift to put everything back.
last = pi[-1]
for j in range(len(pi) - 1, i, -1):
pi[j] = pi[j - 1]
pi[i] = last
yield sub_permutations.next()
```

Example usage would be something like below. Note how the user needs to print the starting permutation first to get all the permutations. Also note how the same top-level coroutine can be used repeatedly to generate the permutations again and again.

```
from perms import permutations
pi = [1, 2, 3]
perm_generator = permutations(pi, 0)
print pi
while perm_generator.next():
print pi
print '-----'
# We can continue using the same coroutines to generate the permutations again.
print pi
while perm_generator.next():
print pi
print '-----'
```

The output of the above code is shown below:

```
[1, 2, 3]
[2, 1, 3]
[2, 3, 1]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]
-----
[1, 2, 3]
[2, 1, 3]
[2, 3, 1]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]
-----
```

## Comments