Is there an efficient way to calculate the optimal swaps required to sort an array? The element of the array can be duplicated, and there is a given upper limit=3. (the elements can be in {1,2,3})
For example:
1311212323 -> 1111222333 (#swaps: 2)
Already found similar questions on Stackoverflow, however, we have new information about the upper limit, that can be useful in the algorithm.
Yes, the upper limit of 3 makes a big difference.
Let w(i, j) be the number of positions that contain i that should contain j. To find the optimal number of swaps, let w'(i, j) = w(i, j) - min(w(i, j), w(j, i)). The answer is (sum over i<j of min(w(i, j), w(j, i))) + (2/3) (sum over i!=j of w'(i, j)).
That this answer is an upper bound follows from the following greedy algorithm: if there are i!=j such that w(i, j) > 0 and w(j, i) > 0, then we can swap an appropriate i and j, costing us one swap but also lowering the bound by one. Otherwise, swap any two out of place elements. The first term of the answer goes up by one, and the second goes down by two. (I am implicitly invoking induction here.)
That this answer is a lower bound follows from the fact that no swap can decrease it by more than one. This follows from more tedious case analysis.
The reason that this answer doesn't generalize past (much past?) 3 is that the cycle structure gets more complicated. Still, for array entries bounded by k, there should be an algorithm whose exponential dependence is limited to k, with a polynomial dependence on n, the length of the arrays.
