In a previous post I posed the question: is there a way to list the permutations of in such a way that any two adjacent permutations are related by just a single swap of adjacent numbers? (Just for fun, let’s call such listings swappy.) Well, as many commenters figured out, the answer is yes. Here’s one possibility:
It’s not hard to check that this list is swappy: that is, that adjacent permutations are always related by an adjacent swap, and that each of the permutations appears exactly once. (Notice that the last and first permutations in the list are also related by a single adjacent swap, which is a nice bonus!)
OK, but what about when ? Or ? Or ? Can we always make a swappy listing of the permutations of the numbers from to ?
The answer to this question turns out to be yes as well, and we can prove it by giving an explicit algorithm which constructs the required list of permutations for any . There are probably lots of ways to do it, but there is a lovely, well-known algorithm to solve this problem (the one I used to make the list above), called the Steinhaus-Johnson-Trotter algorithm. It is named for two mathematicians (Johnson and Trotter) who discovered it independently in the early 1960s, and another (Steinhaus) who previously described a related puzzle. As we’ll see, however, Johnson and Trotter were not actually the first to discover this algorithm; they were about 300 years too late for that, but at least they were the first mathematicians to discover it! More on this later…
Here’s how the algorithm works. First, when , it is very easy to make a swappy list. Here it is:
For larger , the algorithm works recursively: we begin by constructing a swappy list for (using the same algorithm again; though it actually wouldn’t matter, any swappy list for would do). We now take each permutation in our swappy list for and expand it into a list of permutations over as follows: for odd-numbered permutations (that is, the first, third, fifth, … permutations in the swappy list for ), we insert in all possible positions, starting at the end and moving to the beginning. For example, suppose and that the first permutation in the swappy list for is . We take that permutation and turn it into the list of permutations
For even-numbered permutations, we do the same thing, except with starting at the beginning and moving to the end. For example, if the second permutation in the swappy list for is , we turn that into the list
We keep doing this for every permutation in the swappy list for and string the results all together to get (I claim) a swappy list for .
Let’s see how this works for small values of . We already know what the swappy list is for . For , we take the single permutation in the swappy list for , and make it into a list by inserting in every possible position, starting at the end and moving to the beginning:
For , we start with the above swappy list for . We take the first permutation, , and insert moving from the end to the beginning:
Then we take the second permutation, , and insert moving from the beginning to the end:
And finally, we put these two lists together to get the full swappy list for :
You can check for yourself that repeating this procedure on the above list yields the swappy list for that I showed at the beginning of the post; and I hope you can see how to continue the process to get a swappy list for and so on (although of course they get very long quite quickly!).
The only thing remaining is prove that this procedure really does always produce a swappy list. In fact, I’ll let you prove it, but here are some hints. The proof uses induction: that is, it’s enough to prove that is a swappy list (duh!), and that if we assume that the algorithm yields a swappy list for , then it will also successfully produce a swappy list for . To see that the resulting list for has only adjacent swaps, you’ll need to consider two cases: when two adjacent permutations come from inserting in different places in the same permutation from the swappy list for …
and when two adjacent permutations come from different (adjacent) permutations from the swappy list on .
You’ll also need to show that every permutation of length shows up, assuming that every permutation of length shows up in the list for .
Finally, how is it that some non-mathematicians in 17th century England knew about this algorithm? Well, you see, they were doing change ringing!
The idea is that a bunch of people stand in a circle with ropes attached to large bells, and ring them in sequence. However, it’s boring to just ring them in order over and over again, like so they started looking for ways to change the order around. The thing is, the bells are really heavy, and the bells swing from side to side, so you can’t just make a bell ring whenever you want. You can only make small adjustments to the speed at which the bell rings by pulling on the rope. In practice this means that bells can only move one position at a time. For example, if a bell is currently the third bell to ring, you can speed it up a bit so next time it is second, or slow it down a bit so next time it is fourth, but you can’t ring it fast enough to make it first, or slow enough to make it fifth.
Hopefully you can see how this relates: each time all the bells ring in sequence is one permutation. Since bells can only move one position between permutations, all you can do are adjacent swaps. You certainly can have multiple bells swap at once, but the very simple sequence produced by the SJT algorithm (known as “Plain Changes”) has been known by change ringers for a long time.