Minimum swaps to order a list with duplicates

Posted by DrNickBerry@reddit | learnprogramming | View on Reddit | 5 comments

start = ['M', 'L', 'V', 'V', 'E', 'P', 'I', 'A', 'I', 'O', 'L', 'A', 'C', 'O', 'O', 'S', 'C', 'U', 'C', 'I', 'H']

target = ['M', 'O', 'V', 'I', 'E', 'U', 'I', 'P', 'S', 'A', 'L', 'V', 'O', 'I', 'L', 'C', 'C', 'O', 'A', 'C', 'H']

Is there an algorithm to find the minimum number of letter-pair swaps to get from the start list to the target list?

I have read about cycle decompsition, where you iterate through the list indices to find cycles of that swap the paired letters in the fewest moves.

The way I have tried gives a solution with 14 swaps, but I don't think is optimal & suspect this has to do with the duplication of some elements of the list.

Any ideas?

Thanks

[-]

ErasmusDarwin@reddit

If you just want to find the minimum number of swaps, and you don't care how efficient the algorithm for finding it is, then I think I have a decent brute-force answer. Researching the minimum swap problem shows that the solution without duplicates can be found using selection sort and counting the number of swaps. But of course this does have duplicates.

So based on the duplicates in your list (2xA, 3xC, 3xI, 2xL, 3xO, and 2xV), there are 2*3*3*2*3*2 = 216 different permutations. So we create each of those different permutations, mapping each starting letter to its intended ending location, run a selection sort on them, and take the minimum number of swaps out of all 216 possibilities.

In other words, if your starting list was C, A, A, B and the target list was A, A, B, C, you would try a selection sort on both 3, 0, 1, 2 and 3, 1, 0, 2.

3, 0, 1, 2 via selection sort:
0, 3, 1, 2
0, 1, 3, 2
0, 1, 2, 3

3, 1, 0, 2 via selection sort:
0, 1, 3, 2
0, 1, 2, 3

So we see the answer is 2 swaps, and it makes intuitive sense as we used the permutation that keeps the "A" that was already in its correct location.

But if you're looking for a better way, it'd probably be best to model it as a graph with nodes representing the list order and edges representing swaps. Then you could just path-find your way to the most efficient answer. That might get ugly with the memory management for each node, though.

[-]

DrNickBerry@reddit (OP)

Thanks for the steer. Aren't there more permutations than that though? If we just take 6 different items there are 6! = 720 permutations I think, and here we have 21 items, consisting of 12 different items of which 6 are unique and 6 are duplicated.

I have also come up with a brute force solution, but am not happy with it:

remove any elements from list A which are correctly located.
swap any elements in list A where both elements will be correctly located after the swap; remember the swaps.
recursively swap the first incorrectly placed letter in A with every letter that would be correctly placed in that position after the swap, in turn; yield the sequence of swaps when A=B.
Because this method is exhaustive, the shortest sequence yielded contains the minimum number of swaps.

[-]

ErasmusDarwin@reddit

Good catch. So it looks like the correct number of permutations would actually be 2!*3!*3!*2!*3!*2! = 1728. Significantly more than I thought but still manageable in this case. Still, that makes the growth a lot more unwieldy for a more general solution.

I had similar thoughts about letters in the correct place and single swaps that correctly locate both items as being ideal, but at that point, my brain was a bit too fried to be sure that was correct. I think I was worried about issues that don't apply to this problem, like if there were more complicated restrictions on swaps.

I think your steps 3 and 4 are essentially doing a complete DFS of the search space to find the shortest path. If you switch that to BFS or another algorithm that returns the shortest path first, I think that could suddenly be pretty fast.

In fact, putting it all together, I think this would give good results, especially integrating 1 and 2 into the "next move" part of the BFS search so you're never picking a move that disturbs a good result, and you don't bother with checking any other moves from the current node if a double-fix is available.

I'm not sure if only checking the first incorrect letter is still safe in the BFS case. Since we're no longer doing an exhaustive search, it might cause problems. I think I'd have to sit and draw things out on paper to be sure one way or the other. I'm having trouble visualizing whether or not that optimization would make you miss out on future double-fixes.