I have two arrays A and B of the same length.
A and B contain the same elements but in different order.
I need to make A match B by only swapping any two elements within A. I also need to do this in the minimum number of swaps possible. The array(s) can contain duplicate elements.
For example if
A = { 3, 8, 5, 8 }
B = { 8, 8, 3, 5 }
The minimum needed swaps is 2 and the sequence would be
swap(0, 2)
swap(0, 3)
I know how to find how many swaps are needed from sources like here, or here but I cannot find any information on generating the sequence of swaps needed to make A match B. I believe the solution involves directed graphs and cycles but I can't quite figure out a working algorithm that is less than O(n^2) time.