<p>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&#39;)\|^2$ is the swap distance $d(s,s&#39;)$. (from <a href="http://dimacs.rutgers.edu/~graham/pubs/slides/dmsa.pdf" rel="nofollow">Graham Cormode's slides</a>). Not as elegant as Anthony's answer, but quite easy to compute. </p>

<p>Update: please see Oleksandr's comments</p>

CC BY-SA 2.5
2011-01-05T00:55:29.647Z
It seems to me that in Graham's presentation they mean spectral norm ($\|A\|_2$) and not Frobenius norm ($\|A\|_F$).
Oleksandr Bondarenko
CC BY-SA 2.5
2011-01-05T02:40:29.437Z
although if all you want to do is count the differences, then the square of the frobenius norm should work right ?
Suresh Venkat
CC BY-SA 2.5
2011-01-05T02:41:04.910Z
which is of course the Hamming distance for 0-1 matrices
Suresh Venkat
CC BY-SA 2.5
2011-01-05T08:48:29.027Z
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
CC BY-SA 2.5
2011-01-05T09:32:30.643Z
Oleksandr: So I suppose that you interpret "swapping" as "exchanging two adjacent elements"?
Anthony Labarre
CC BY-SA 2.5
2011-01-05T11:26:43.333Z
@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
CC BY-SA 2.5
2011-01-05T16:11:30.360Z
I think Oleksandr is right here. I'll edit the answer
Suresh Venkat
CC BY-SA 3.0
2011-09-07T13:58:50.830Z
@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
CC BY-SA 2.5
2011-01-04T20:59:20.760Z
2011-01-05T16:12:15.993Z
2011-01-05T16:12:15.993Z
Suresh Venkat
<p>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 <a href="http://en.wikipedia.org/wiki/Cycle_notation">disjoint cycle decomposition</a> 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.</p>

CC BY-SA 3.0
2012-10-05T15:08:41.127Z
Despite voting for this a long time ago, it just clicked today.  Like a Rubik's cube, right :D?
sova
CC BY-SA 2.5
2011-01-04T20:54:54.210Z
2011-01-04T20:54:54.210Z
Anthony Labarre
<p>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 <em>A</em> and a sorted ordering <em>B</em>, what is an efficient way to calculate the optimal number of transpositions to get from <em>A</em> to <em>B</em> ?</p>

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

<pre><code>1 2 4 3
</code></pre>

<p>has one transposition (transposition 4 and 3) to make it</p>

<pre><code>1 2 3 4
</code></pre>

<p>Something like</p>

<pre><code>1 7 2 5 9 6
</code></pre>

<p>requires 4 transpositions (7, 2), (7, 6), (6,5), (9, 7)</p>

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

<ds.algorithms><co.combinatorics><sorting>
Minimum number of transpositions to sort a list
sova
# Minimum number of transpositions to sort a list

(Asked by: username_0 on 2011-01-04)

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.

**Tags:** ds.algorithms, co.combinatorics, sorting


---

## 2 answers

### Answer by username_3 on 2011-01-04. Score: 23 | Accepted answer

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](http://en.wikipedia.org/wiki/Cycle_notation) 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.

> **Comments:**
> **username_0**: Despite voting for this a long time ago, it just clicked today.  Like a Rubik's cube, right :D?  

---

### Answer by username_1 on 2011-01-04. Score: 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](http://dimacs.rutgers.edu/~graham/pubs/slides/dmsa.pdf)). Not as elegant as Anthony's answer, but quite easy to compute.

Update: please see Oleksandr's comments

> **Comments:**
> **username_2**: It seems to me that in Graham's presentation they mean spectral norm ($\|A\|_2$) and not Frobenius norm ($\|A\|_F$).  
> **username_1**: although if all you want to do is count the differences, then the square of the frobenius norm should work right ?  
> **username_1**: which is of course the Hamming distance for 0-1 matrices  
> **username_2**: 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.  
> **username_3**: Oleksandr: So I suppose that you interpret "swapping" as "exchanging two adjacent elements"?  
> **username_2**: @username_3: Yes. But the author of the question seems to use swapping for transposition. (This is seen especially from his second example.)  
> **username_1**: I think Oleksandr is right here. I'll edit the answer  
> **username_4**: @username_1 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"?  

---

