Visualizing Permutations

At some point a few years ago, I got interested in permutation algorithms and implemented a few that were in Knuth as well as gathered some that were floating around the internet. I never did anything with them, until I saw Aldo Cortesi's excellent sorting visualizations which reminded me of a figure from Knuth, and inspired me to create some visualizations of my own using Aldo's code.

Lexicographic Permutations

Informally, the permutations of a set are all possible orderings of its members. The permutations of the set {1,2,3}, are:

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

This particular ordering of permutations is in lexicographic order; it's listed in the same order as it would be in the dictionary. There are many well-known algorithms for generating permutations in lexicographic order. Here is my version of one such algorithm; go read Knuth if you're at all interested in learning more.

Here's what a lexicographic permutation of four elements looks like:

It's easy to see that each element gets its turn at the top of the list, and that each time a new element goes to the top the remainder of the list is sorted.

Single-transposition Permutations

It is an interesting and non-obvious fact that there's a way to permute any given set by only switching the positions of one pair of elements per iteration. This permutation is deeply related to the Gray code, which if you haven't heard of, I highly recommend you go read about. The Knuth paper I mentioned aleady has a superb bit on the Gray code.

This image demonstrates clearly that at each step, there is exactly one crossing. My implementation of this algorithm is also on github.

CLP Permutation

I know very little about this algorithm, except that I got it from a message to comp.lang.python where it's attributed to Alex Martelli, Duncan Smith, and somebody named Anton (Anton Vredegoor?). Despite the crazy number of switches, and the fact that it reorders the list it's passed, it's actually crazy fast.

I'd love to hear from anyone with more info on this algorithm; my slightly modified version is here.

Odds and Ends

Well, that's it, just wanted to post some fun pictures of permutations, I hope you enjoyed it. The code I used to generate the pictures is derived from Aldo Cortesi's wonderful sortvis, and all my modifications to it are available on github as well.

If you want bonus points, I never got around to implementing Knuth's algorithm E (it's given towards the end of this), and I'd love for somebody else to do my work for me. If you're tough enough, that is.