16

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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
sova
  • 263
  • 2
  • 5
  • what if you can just swap neighbors? how can I figure out the minimum number of swaps? –  Sep 07 '11 at 05:13

2 Answers2

23

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.

Anthony Labarre
  • 3,264
  • 1
  • 25
  • 33
  • Despite voting for this a long time ago, it just clicked today. Like a Rubik's cube, right :D? – sova Oct 05 '12 at 15:08
12

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.

Update: please see Oleksandr's comments

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • It seems to me that in Graham's presentation they mean spectral norm ($|A|_2$) and not Frobenius norm ($|A|_F$). – Oleksandr Bondarenko Jan 05 '11 at 00:55
  • although if all you want to do is count the differences, then the square of the frobenius norm should work right ? – Suresh Venkat Jan 05 '11 at 02:40
  • which is of course the Hamming distance for 0-1 matrices – Suresh Venkat Jan 05 '11 at 02:41
  • 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. – Oleksandr Bondarenko Jan 05 '11 at 08:48
  • Oleksandr: So I suppose that you interpret "swapping" as "exchanging two adjacent elements"? – Anthony Labarre Jan 05 '11 at 09:32
  • @Anthony Labarre: Yes. But the author of the question seems to use swapping for transposition. (This is seen especially from his second example.) – Oleksandr Bondarenko Jan 05 '11 at 11:26
  • I think Oleksandr is right here. I'll edit the answer – Suresh Venkat Jan 05 '11 at 16:11
  • @Suresh Venkat Although this question is a bit older, don't you think it would be prudent to change the question to use "transposition" in place of "swap"? – Tyson Williams Sep 07 '11 at 13:58