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 2The list [0, 1, 0, 0] requires 1 transposition:[0, 1, 0, 0] // Start[0, 0, 0, 1] // Swap index 1 and 3The 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.
Efficiently finding the minimum number of transpositions needed to sort a list
ds.algorithms;sorting;permutations;edit distance
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.