Minimum swaps to order a list with duplicates
Posted by DrNickBerry@reddit | learnprogramming | View on Reddit | 1 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
Lumpy_Ad7002@reddit
Perhaps r/algorithms might be better for this question