Permuting permutations

As you probably know, there are n! (n factorial) different ways to put the numbers from 1 through n (or any set of n distinct objects) in a list. For example, here are the 4! = 24 different lists containing the numbers 1 through 4:

Each such list is called a permutation. Now, think about the above picture: the entire picture itself represents a list (read, say, top to bottom and then left to right) of all the permutations of \{1, \dots, 4\}. That is, it’s a permutation of permutations! And of course, there are 24! = 620448401733239439360000 (that is, about 6.2 \times 10^{23}, i.e 620 sextillion, i.e six hundred thousand million million million, i.e. if you could count one trillion numbers every second, it would take you nineteen thousand years to count that high) different ways of putting the 24 permutations in some order.

Look at the particular order given in the picture above. To go from the first permutation (1234) to the second (2134) requires only swapping two adjacent numbers—namely, 1 and 2.

However, going from 2134 to the third permutation in the list (3214) requires more than just a swap—the 1, 2, and 3 all get reshuffled.

Consider also the transition from the sixth permutation (1324) to the seventh (4321, at the top of the second column). It also requires just a swap of two numbers (1 and 4)—but they are not adjacent.

Note by “adjacent” I mean adjacent in the list, not adjacent as numbers. For example, going from the penultimate (3412) to the final permutation (3142) also involves swapping 1 and 4, but this time they are adjacent.

Here’s the question: can we put these 24 permutations in some order so that the only kind of transition between successive permutations is a swap of two adjacent numbers?

Obviously, exhaustively searching through all 620 sextillion orders is out of the question, so we’ll have to be a bit more clever.

Rather than give away the answer, I think I’ll just stop and let you think about it. If you haven’t seen it before, this problem really makes for a great exploration, with all kinds of interesting structure and connections to discover. Can you figure out an ordering that works—or explain why it’s not possible? You might also want to try it for some simpler cases—say, permutations of \{1,2\} and of \{1,2,3\}. If you figure it out for \{1, \dots, 4\}, how about \{1, \dots, 5\}?

In another post I’ll give the answer, and explain why people in 17th century England (!) cared about this problem (don’t give it away in the comments if you know!).

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

11 Responses to Permuting permutations

  1. decourse says:

    Here’s what I found out without cheating:

    Let G be a graph where the vertices are permutations, and there is an edge between two vertices if there is a single element swap which transforms one permutation into the other. The question is asking if G has a Hamiltonian cycle. G is clearly vertex-transitive, so if the Lovász conjecture is true, then it does indeed have a Hamiltonian cycle. This strongly suggests that it can be done.

    Of course, I couldn’t leave it at that. I did eventually cheat, and I now know who S, J and T are.

  2. Drawing out the graph, it turns out to be a truncated octahedron. The truncated octahedron is also the order 4 permutohedron but the vertices don’t match up. Mysterious!

  3. lkuty says:

    I once read two very interesting articles about it. I will put references to them in your next post if you don’t mention them in your main text. However one article is an old writing in french. I don’t know if it has been translated. I like the way you bring things in this article. Step by step and then you leave us with a question :)

  4. asdf says:

    def printer(n):
    if n == 1:
    yield [1]
    elif n > 1:
    for i, l in enumerate(printer(n – 1)):
    for j in range(n)[::-1 if i % 2 == 0 else 1]:
    yield l[:j] + [n] + l[j:]

    for i in printer(4):
    print i

  5. TomC says:

    Am I considered extremely ‘less traveled’ when I tell you that I just wrote the sequence down on paper with a sharpy in about 2 minutes? No math, no proof, just intuition?

  6. ck says:

    by induction i realise we can do that for permutations of all possible N. But i don’t know why “people in 17th century England (!) cared about this problem”. Looking forward to the next post…

  7. Pingback: The Steinhaus-Johnson-Trotter algorithm | The Math Less Traveled

  8. Pingback: Diagrams! | The Math Less Traveled

Comments are closed.