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
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
False otherwise. A "nobody" coroutine which always
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
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] -----