# 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.