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]
-----