Last time on FAIC I described a simple recursive algorithm for generating all permutations of the first n whole numbers: if you have all the permutations of the first n-1 whole numbers, you just insert the nth whole number at each of n positions in each permutation. So if we had all the permutations of {0, 1, 2} and we wanted all the permutations of {0, 1, 2, 3}, we just start listing permutations of {0, 1, 2} with the 3 stuck in each of 4 places:
{3, 0, 1, 2},
{0, 3, 1, 2},
{0, 1, 3, 2},
{0, 1, 2, 3}, That does it for {0, 1, 2}...
{3, 0, 2, 1},
{0, 3, 2, 1},
{0, 2, 3, 1},
{0, 2, 1, 3}, That does it for {0, 2, 1}...
and continue to get the 24 permutations.
This works and we could write code for it, but there’s an interesting pattern in each section of four. Within each section, two adjacent permutations differ solely by swapping one pair. That is, the difference between the first and second permutation is a swap of the first pair. The difference between the second and third is a swap of the second pair, and so on. The pattern gets broken however when we start in on the next section; the difference between {0, 1, 2, 3} and {3, 0, 2, 1} is hard to characterize as a bunch of swaps of adjacent items.
But wait a moment. What if we reverse the order of the second section?
{3, 0, 1, 2},
{0, 3, 1, 2},
{0, 1, 3, 2},
{0, 1, 2, 3}, That does it for {0, 1, 2}...
{0, 2, 1, 3},
{0, 2, 3, 1},
{0, 3, 2, 1},
{3, 0, 2, 1}, That does it for {0, 2, 1}...
Holy goodness, we suddenly have our desired property! (Can you list what the sixteen remaining permutations are in order that I omitted? Hint: The next one is {3, 2, 0, 1}. The bottommost graph below gives the answer.)
Here’s an interesting way to characterize this property. Suppose we make a graph where the nodes are all the possible permutations and there is an edge between any two nodes that differ only by a swap of adjacent elements. The graphs for the two-element and three-element permutations are:[1. Obviously I have mad PowerPoint skillz.]
In these first two cases it is pretty obvious how we can enumerate permutations in an order such that each subsequent permutation differs from the previous by swapping two adjacent elements. You just “run around the graph”. But for the four-element permutations, it is not so obvious from the graph:[2. An interesting property of this graph is that if you place the vertices at their coordinates in a four-dimensional space — that is, one point at (0, 1, 2, 3), one point at (0, 1, 3, 2), and so on, and keep the edges attached as shown here, then the resulting four-dimensional object actually “fits” into three dimensions. Not only does it fit into three dimensions, but if you made an infinite number of those three-dimensional shapes and “filled them in” as solids, you could fit them together to perfectly “tile” three-dimensional space, the same way you can “tile” three-d space with infinitely many cubes. In fact this is true of any permutation graph; the n-dimensional shape you make actually fits into n-1 dimensions and tiles the n-1 dimensional space. You can see this in the lower dimension quite easily; clearly the three-element permutation graph forms a flat hexagon in three-space, and a flat hexagon tiles two-space.]
What we want to find here is one of the Hamiltonian tours of the graph; that is, the path that makes a complete circuit of the graph visiting every node exactly once. Our proposed algorithm finds this Hamiltonian tour:
Next time on FAIC: we’ll actually write the code that generates a Hamiltonian tour of the permutation graph for any size of permutation.
Fabulous adventures in coding 
Reading through the post, I was gearing up to make a comment similar to your second footnote. I assume you’re not leaving the geometry of this polyhedron as a puzzle, so then it’s only natural to point to the canonical example of such a shape: http://en.wikipedia.org/wiki/Truncated_octahedron.
Thanks for the great post. I love reading your theoretical posts as much as your posts on language design, and am hopeful for a post on category theory.
Wow.! Just great another post..
Nice post – thx! Is it true that these graphs are always “planar” (the geometry was hard to miss). such properties are interesting too, don’t you agree?
By “planar” you mean that the graph can be squashed onto a plane and there is a configuration such that no two edges cross, it is certainly the case that the first three are planar. I see no reason why the fourth, fifth, etc, cases, have to be planar.
However there is another way in which the graphs are “planar” that I alluded to in my post. In the 3-element case the hexagon whose coordinates are (0,1,2), (0, 2, 1), etc, in 3-space inhabits a flat plane. The truncated octohedron whose coordinates are (0,1,2,3), (0,1,3,2), and so on in 4 space inhabits a “flat plane” of 4-space; that it, you can take a “flat slice” of the 4-d space and make a 3-d space that the permutohedron lives in. In this sense the graphs always “define a plane” of the higher-dimensional space they live in.
This property follows naturally from the fact that the points that are on the vertices of the permutohedron have the same sum of their elements. Do you see why?
Hmm… probably using mathematical induction on the dimensions “n” ?
[I actually meant the first definition of planarity, but of course I see that it doesn’t hold true for >= 4 dimensions]
A very good and free editor for such graphs can be found here: http://www.yworks.com/en/products_yed_about.html
You can even import a simple list of your nodes and their connections, and it will automatically arrange it. I use it often.
Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1339
Hi Eric,
If you’ve not met it already, you might be interested to hear about the peculiar English practice of change ringing (http://en.wikipedia.org/wiki/Change_ringing), where huge bells (up to 4 tons) are rung in neat permutations. The weight of each bell imposes a restriction in how permutations can be rung: its speed can only be changed enough to alter its position in the perm by one place – just as in your algorithm above.
Ringers care a great deal about ringing all possible permutations available for a given number of bells (we call it an “extent”), and doing so without any repeats. It takes around 3 hours to ring the extent on seven bells, and it’s not really practical to ring the extent with any more. Ringing on higher numbers often involves going for a peal of 5000 permutations, starting and ending with the bells all in order, and trying to navigate to the more pleasant-sounding orders without repeating any. Each ringer gets one bell, and complex systems have evolved to make sure they all know what to do at the right time.
If you’re interested there’s a great introductory presentation at http://www.boojum.org.uk/ringing/mathsclub-slides.pdf, and a huge pile of links at http://ringing.info/. A page at http://jaharrison.me.uk/Ringing/RingingShapes/index.html talks a little about permutohedra (good word, BTW).
I should also have mentioned this page: http://dove.cccbr.org.uk/dove.php?numPerPage=50&searchCountry=USA – it’s a list of towers in the US with ringable bells. If you’d like to see change ringing in action then you should visit one – or let me know if you’re ever near London.