# Efficiently finding the minimum number of transpositions needed to sort a list

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.

• Duplicate of cstheory.stackexchange.com/questions/4096/… Oct 2, 2012 at 7:19
• I think that the answer(s) posted here should be merged to question 4096. Oct 2, 2012 at 12:16
• @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. Oct 2, 2012 at 15:59
• 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. Oct 2, 2012 at 16:21
• @emchristiansen Oops, sorry, I haven't noticed that... Oct 3, 2012 at 6:28