How many changes to get back to rounds?

1 Problem statement

The problem was posed on math.stackexchange:

Consider the following game. I give you a deck of n cards arbitrarily shuffled. Your goal is to sort the deck in r moves. In each move, you may swap the positions of two adjacent cards. You may also swap an arbitrary number of pairs of adjacent cards in parallel in a single move, as long as the pairs are disjoint. For example, in one move you may in parallel swap cards 1,2 and also 4,5. But you cannot swap 1,2 and then swap 2,3 in one move, since the swaps have an overlap; this would require 2 moves. You also cannot swap 1,4 in one move, since these are not adjacent.

How many moves m(n) are necessary and sufficient to guarantee that the deck can always be sorted, as a function of n?

The poster conjectured that for n ≥ 3, the answer might be n, with a proof for the cases n = 3,4.

2 Reframing: a bellringing problem

As a former bellringer, I immediately recognised that the poster’s valid “moves” corresponded to valid bellringing changes. In bellringing, every bell rings once, in some order. This permutation is one row. This is followed by the next row, in which every bell again rings once, in some order. The difference between the two rows is a change – and the source of the idiom “ringing the changes”. When all the bells ring in order (from the highest note to the lowest), this is called rounds. Typically, a piece of bellringing will begin with a period of rounds, and then move into changes, with the row (or permutation) changing repeatedly, and then return to rounds.

We could reframe the stackexchange question as:

The bells have been ringing changes for some time and have reached an arbitrary permutation. How many changes do we need to guarantee we can return to rounds?

Is the poster's conjecture plausible? On the one hand, it might seem remarkable that -- say we are ringing twelve bells, with 38 million possible permutations, and we've taken a path through some 17 million, no repeats -- that we can reverse this path in a mere 12 changes. On the other hand, clearly no single bell can be more than n-1 places away from its home position, so perhaps the conjecture is indeed sensible.

3 Diversions: The Cayley graph

There are lots of bellringers who like maths, and lots of non-bellringing mathematicians who have taken an interest in the mathematics of bellringing; in short, there are any number of projects and articles about the mathematics of bellringing to be found on the internet. Perhaps one of them had already investigated this problem?

What I found in my internet search was the Cayley graph on Sn with valid “moves” or bellringing changes as generators. Our question here can now be reframed as – what is the diameter of this Cayley graph? However, most projects then moved on to finding Hamiltonian cycles in the graph (ways of moving through all possible permutations without a repeat). The question of the diameter of the graph was not explored.

A related graph is better known: if we just allow a single adjacent swap in each move, the resulting Cayley graph is a permutahedron, and its diameter is n(n-1) 2, with a unique element having that path length from rounds: the reversed permutation [n,n- 1,…,1]. I spent some time trying to see the full bellringing Cayley graph as “shortcuts” through the permutahedron, but I wasn’t able to identify any useful pattern here.

Since it’s fairly easy to define the set of valid moves, or generators, in a recursive function, I did build the Cayley graphs for n = 3,…,8 in SageMath and obtain their diameters. Finding these diameters involves computing O(n!) paths and SageMath didn’t terminate for n = 9, but did confirm the stackexchange poster’s conjecture for these small n. For small n (4, 5, 6), I also asked SageMath to list the vertices (permutations) at the maximum distance from rounds. Notable here is that, unlike the permutahedron, there were many of these (growing with n) – always including the “reversed” permutation.

4 Homing in: Bubble sort

The permutahedron is also known as the bubble sort graph, because bubble sort works by swapping adjacent elements (if necessary). This brings us back to the stackexchange user’s framing: they are trying to sort their deck of cards. We can think about the problem as some kind of parallelised bubble sort.

From bellringing, we already know a way to move from the “reversed” permutation into rounds in n moves: it is called plain hunting and is quite straightforward: each bell moves one place in every move, until it reaches first or last place, in which case it waits there one move. Plain hunting for seven and eight bells respectively can be drawn diagrammatically like

123456712345671234567812345678

We see that the total number of crossings in this solution is n(n - 1): twice as many as the diameter of the permutahedron. Many of the bells are wandering away from their destination before homing in on it. However, the permutahedron solution is not immediately parallelisable:

123456123456

Incidentally, the permutahedron solution and the “plain hunt” solution, if converted to braids by taking all crossings to be positive (left over right), are equivalent under Artin’s braid relations. We might briefly wonder if there is a solution to be found in braid theory: if we write down a braid which brings each element in turn “home” as directly as possible, always using positive crossings, will the step number of this braid correspond to the number of passes needed? I wasn’t sure if the braid with using this naive approach would always be equivalent (under the braid relations) to the braid corresponding to the “best” sort in our sense, and in any case no efficient algorithm is known for finding the step number.

So, back to bubble sort. The “plain hunt” sort gives us our cue. We propose the following algorithm:

This algorithm is simple to implement; here it is handling a couple of the “worst case” permutations for n = 6, identified by SageMath using the Cayley graph:

123456123456123456123456

5 Wrapping up the proof

I didn’t do the work of proving that this algorithm can always sort a permutation in n moves myself. A little judicious searching turned up its name: odd-even (bubble) sort and along with a name, the fact that it is known to require ≤ n passes to sort any array of numbers. I didn’t actually even check the proof, but it seems to be a fairly well-known result. So we have that we can guarantee to sort the stackexchange user’s card deck in ≤ n moves, or return to rounds in ≤ n changes.

To conclude the proof that n is indeed the magic number, need to show that there are indeed permutations that cannot be sorted in < n passes (e.g. by using some other magic algorithm we have not yet considered). We consider the “reversed” permutation (in fact, the argument will work for any permutation with [n,n- 1,…] or […,2,1]):

6 Discussion

Ultimately, the diversion into Cayley graphs, permutahedra, and even a little braid theory turned out to be not helpful to the problem. We can answer the poster’s question with a brief description of the odd-even bubble sort algorithm and an outline proof that it requires ≤ n passes, combined with the easy proof that there are indeed permutations requiring all n passes. The braid-like diagrams are a nice way of showing the algorithm at work. Everything else can be cleaned out of the answer. This seems to happen a lot in maths. You can spend a long time thinking about something and pursuing potentially interesting mathematical pathways, only to arrive at an answer that is, ultimately, much more straightforward.

So mainly what I wanted to type up here is the route through my thought process, which took me (with the help of the internet and SageMath) from the question about sorting card decks → bellringing → Cayley graphs → permutahedra → bubble sort and thence to a solution. Also, permutahedra are cool. Check 'em out.