<p>Unfortunately, the problem is NP-hard in general, according to Amir, Hartman, Kapah, Levy and Porat (see <a href="http://epubs.siam.org/doi/abs/10.1137/080712969" rel="nofollow">http://epubs.siam.org/doi/abs/10.1137/080712969</a>), even if each symbol appears at most three times. <strike>I didn't find a mention of a constant factor approximation algorithm, or of something reasonably fast to tackle the problem. Are there any additional restrictions you can think of in your case?</strike></p>

<p>EDIT: the authors also give a 3/2-approximation algorithm, but I don't know if it's good enough for your purposes.</p>

CC BY-SA 3.0
2012-10-02T15:56:40.920Z
Thanks for the reference. I'm dealing with pixel values, so lists of integers in [0, 255]. A common list length is 256 elements.
emchristiansen
CC BY-SA 3.0
2016-01-01T00:44:46.093Z
Can you prove, that when you have a solution (minimal sorting sequence of transposition), you always swap large number on the left with a smaller number on the right?
Ivan Kuckir
CC BY-SA 3.0
2012-10-02T11:49:33.020Z
2012-10-16T12:05:51.840Z
2012-10-16T12:05:51.840Z
Anthony Labarre
<p>I'd like an efficient method for calculating the minimum number of transpositions needed to sort a list. I don't need to know what the transpositions actually are.</p>

<p>For example, the list [1, 1, 2, 0] requires 2 transpositions:</p>

<pre><code>[1, 1, 2, 0] // Start
[1, 1, 0, 2] // Swap index 2 and 3
[0, 1, 1, 2] // Swap index 0 and 2
</code></pre>

<p>The list [0, 1, 0, 0] requires 1 transposition:</p>

<pre><code>[0, 1, 0, 0] // Start
[0, 0, 0, 1] // Swap index 1 and 3
</code></pre>

<p>The list [2, 2, 2, 2] requires 0 transpositions because it is already sorted.</p>

<p>Some meta information:
1) The list may have repeated elements, so simply using the <a href="https://cstheory.stackexchange.com/questions/4096/minimum-number-of-transpositions-to-sort-a-list">Cayley distance between the sort and the identity permutation will not work</a>.
2) This <a href="https://mathoverflow.net/questions/106836/distances-on-generalizations-of-the-symmetric-group">Math Overflow question</a> is related.</p>

CC BY-SA 3.0
2012-10-02T07:19:14.350Z
Duplicate of http://cstheory.stackexchange.com/questions/4096/minimum-number-of-transpositions-to-sort-a-list
derekhh
CC BY-SA 3.0
2012-10-02T12:16:38.120Z
I think that the answer(s) posted here should be merged to question 4096.
Tsuyoshi Ito
CC BY-SA 3.0
2012-10-02T15:59:01.307Z
@derekhh, this is not a duplicate (or at least the interpretation of the post is different in the other question). I linked to question 4096 in the original post.
emchristiansen
CC BY-SA 3.0
2012-10-02T16:21:17.923Z
Question 4096 does not state that given elements are distinct.  Unfortunately, all the answers posted there silently assumed this, and this oversight can be corrected by merging the answer(s) here to there.
Tsuyoshi Ito
CC BY-SA 3.0
2012-10-03T06:28:42.333Z
@emchristiansen Oops, sorry, I haven't noticed that...
derekhh
<ds.algorithms><sorting><permutations><edit-distance>
Efficiently finding the minimum number of transpositions needed to sort a list
emchristiansen
# Efficiently finding the minimum number of transpositions needed to sort a list

(Asked by: username_0 on 2012-10-02)

I'd like an efficient method for calculating the minimum number of transpositions needed to sort a list. I don't need to know what the transpositions actually are.
For example, the list [1, 1, 2, 0] requires 2 transpositions:
[1, 1, 2, 0] // Start
[1, 1, 0, 2] // Swap index 2 and 3
[0, 1, 1, 2] // Swap index 0 and 2

The list [0, 1, 0, 0] requires 1 transposition:
[0, 1, 0, 0] // Start
[0, 0, 0, 1] // Swap index 1 and 3

The list [2, 2, 2, 2] requires 0 transpositions because it is already sorted.
Some meta information:
1) The list may have repeated elements, so simply using the Cayley distance between the sort and the identity permutation will not work.
2) This Math Overflow question is related.

**Tags:** ds.algorithms, sorting, permutations, edit-distance

> **Comments:**
> **username_1**: Duplicate of http://cstheory.stackexchange.com/questions/4096/minimum-number-of-transpositions-to-sort-a-list  
> **username_2**: I think that the answer(s) posted here should be merged to question 4096.  
> **username_0**: @username_1, this is not a duplicate (or at least the interpretation of the post is different in the other question). I linked to question 4096 in the original post.  
> **username_2**: Question 4096 does not state that given elements are distinct.  Unfortunately, all the answers posted there silently assumed this, and this oversight can be corrected by merging the answer(s) here to there.  
> **username_1**: @username_0 Oops, sorry, I haven't noticed that...  

---

## 1 answers

### Answer by username_3 on 2012-10-02. Score: 7 | Accepted answer

Unfortunately, the problem is NP-hard in general, according to Amir, Hartman, Kapah, Levy and Porat (see <http://epubs.siam.org/doi/abs/10.1137/080712969>), even if each symbol appears at most three times. I didn't find a mention of a constant factor approximation algorithm, or of something reasonably fast to tackle the problem. Are there any additional restrictions you can think of in your case?

EDIT: the authors also give a 3/2-approximation algorithm, but I don't know if it's good enough for your purposes.

> **Comments:**
> **username_0**: Thanks for the reference. I'm dealing with pixel values, so lists of integers in [0, 255]. A common list length is 256 elements.  
> **username_4**: Can you prove, that when you have a solution (minimal sorting sequence of transposition), you always swap large number on the left with a smaller number on the right?  

---

