15
$\begingroup$

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.

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

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.

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

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

$\endgroup$
  • $\begingroup$ It seems to me that in Graham's presentation they mean spectral norm ($\|A\|_2$) and not Frobenius norm ($\|A\|_F$). $\endgroup$ – Oleksandr Bondarenko Jan 5 '11 at 0:55
  • $\begingroup$ although if all you want to do is count the differences, then the square of the frobenius norm should work right ? $\endgroup$ – Suresh Venkat Jan 5 '11 at 2:40
  • $\begingroup$ which is of course the Hamming distance for 0-1 matrices $\endgroup$ – Suresh Venkat Jan 5 '11 at 2:41
  • $\begingroup$ 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. $\endgroup$ – Oleksandr Bondarenko Jan 5 '11 at 8:48
  • $\begingroup$ Oleksandr: So I suppose that you interpret "swapping" as "exchanging two adjacent elements"? $\endgroup$ – Anthony Labarre Jan 5 '11 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.