The Steinhaus-Johnson-Trotter algorithm

In a previous post I posed the question: is there a way to list the 4! = 24 permutations of 1,2,3,4 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 24 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 n = 5? Or 6? Or 927? Can we always make a swappy listing of the permutations of the numbers from 1 to n?

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 n. 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 n = 1, it is very easy to make a swappy list. Here it is:

For larger n, the algorithm works recursively: we begin by constructing a swappy list for n-1 (using the same algorithm again; though it actually wouldn’t matter, any swappy list for n-1 would do). We now take each permutation in our swappy list for n-1 and expand it into a list of permutations over n as follows: for odd-numbered permutations (that is, the first, third, fifth, … permutations in the swappy list for n-1), we insert n in all possible positions, starting at the end and moving to the beginning. For example, suppose n = 4 and that the first permutation in the swappy list for 3 is . We take that permutation and turn it into the list of permutations

For even-numbered permutations, we do the same thing, except with n starting at the beginning and moving to the end. For example, if the second permutation in the swappy list for 3 is , we turn that into the list

We keep doing this for every permutation in the swappy list for n-1 and string the results all together to get (I claim) a swappy list for n.

Let’s see how this works for small values of n. We already know what the swappy list is for n=1. For n=2, we take the single permutation in the swappy list for 1, and make it into a list by inserting in every possible position, starting at the end and moving to the beginning:

For n = 3, we start with the above swappy list for 2. 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 n=3:

You can check for yourself that repeating this procedure on the above list yields the swappy list for n = 4 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 n = 5 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 n-1, then it will also successfully produce a swappy list for n. To see that the resulting list for n has only adjacent swaps, you’ll need to consider two cases: when two adjacent permutations come from inserting n in different places in the same permutation from the swappy list for n-1

and when two adjacent permutations come from different (adjacent) permutations from the swappy list on n-1.

You’ll also need to show that every permutation of length n shows up, assuming that every permutation of length n-1 shows up in the list for n-1.

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 123456 123456 123456\dots 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.

About these ads
This entry was posted in combinatorics, pattern, solutions and tagged , , , , , . Bookmark the permalink.

9 Responses to The Steinhaus-Johnson-Trotter algorithm

  1. Ryan Yates says:

    I was wondering if your post would lead to change ringing. Rebekah and I have been reading British mystery novels for a while now and one of the Dorothy Sayers books features a lot of change ringing. At one point long ago I wrote some code to generate “swappy” lists but failed to make it general. I was generating data to look at the connection between cwatsets (http://en.wikipedia.org/wiki/Closure_with_a_twist) and graphs.

    • Brent says:

      Ah, Lord Peter, eh? We’ve read a few but I don’t think we’ve read the one with lots of change ringing, do you happen to remember which one it is? Anyway, I had never heard of cwatsets, they sound intriguing but I couldn’t get a good intuitive sense for them from the Wikipedia page. Where do they come up?

      • Ryan Yates says:

        “The Nine Tailors” is the book. As far as I know cwatsets only showed up as a topic of undergraduate research for a few years.

  2. Nick Johnson says:

    Very nice! This seems closely related to the gray code – in that it’s the equivalent form for permutations instead of bit flips.

    • Brent says:

      Yes, it is definitely related! The Wikipedia article for the SJT algorithm explains (at least part of) the precise relationship to gray code.

  3. Jonathan says:

    I loved the change ring connection!

  4. TomC says:

    Thanks for the answer to the question. What makes me smile is that I’ve never heard of the Steinhaus–Johnson–Trotter algorithm (didn’t do much graph-theory at university), but I instinctively used the Even’s speedup algorithm described in the Wikipedia article when I created the permutations by hand. I guess some solutions really ARE obvious,

  5. John Baker says:

    An excellent bit of computer science/mathematics with a ringing historical endorsement.

  6. Pingback: Diagrams! | The Math Less Traveled

Comments are closed.