# Minimum number of transpositions to sort a list

In trying to devise my own sorting algorithm, I'm looking for the optimal benchmark to which I can compare it. For an unsorted ordering of elements A and a sorted ordering B, what is an efficient way to calculate the optimal number of transpositions to get from A to B ?

A transposition is defined as switching the position of 2 elements in the list, so for instance

1 2 4 3


has one transposition (transposition 4 and 3) to make it

1 2 3 4


Something like

1 7 2 5 9 6


requires 4 transpositions (7, 2), (7, 6), (6,5), (9, 7)

Update (9/7/11): question changed to use "transposition" instead of "swaps" to refer to non-adjacent exchanges.

• what if you can just swap neighbors? how can I figure out the minimum number of swaps?
– user6453
Sep 7 '11 at 5:13

If you're only dealing with permutations of $n$ elements, then you will need exactly $n-c(\pi)$ swaps, where $c(\pi)$ is the number of cycles in the disjoint cycle decomposition of $\pi$. Since this distance is bi-invariant, transforming $\pi$ into $\sigma$ (or $A$ into $B$, or conversely) requires $n-c(\sigma^{-1}\circ\pi)$ such moves.

• Despite voting for this a long time ago, it just clicked today. Like a Rubik's cube, right :D?
– sova
Oct 5 '12 at 15:08

The swap distance can also be isometrically embedded in Euclidean space. For each string s, construct a matrix $M(s)$ where $M_{ij} = 1$ if $i$ occurs before $j$ and is zero otherwise. Then the Frobenius distance $\|M(s) - M(s')\|^2$ is the swap distance $d(s,s')$. (from Graham Cormode's slides). Not as elegant as Anthony's answer, but quite easy to compute.

• It seems to me that in Graham's presentation they mean spectral norm ($\|A\|_2$) and not Frobenius norm ($\|A\|_F$). Jan 5 '11 at 0:55
• You're right about equality between the square of Frobenius norm and Hamming distance. I'd like to add that Hamming distance divided by $2$ equals swap distance. But the question was about transposition distance ("A swap is defined as switching the position of 2 elements in the list") and not about swap distance. What concerns spectral norm it is the square of it equals to swap distance. Jan 5 '11 at 8:48