How to find the shortest sequence of swaps between two different permutations?

Question

I am looking some kind of an algorithm that would help me to solve a task that stands before me. I need to find out a method to find (NOT only count) all swaps (exchange of two elements) in a given permutation which is required to transform it into another given permutation. It would be great if the method could find the minimum number of swaps leading from one permutation to another. Could anybody provide me with a tip or a full solution to this problem?

Answer 1

First determine where each value should go. You'll then find cycles of moves. Take for instance this data:

source: [5, 3, 0, 7, 1, 6, 4, 8]
target: [3, 1, 0, 4, 5, 7, 8, 6]
(index:  0  1  2  3  4  5  6  7  ) 

Then we can derive that the value at index 0 (which is 5) should go to index 4, and the one at index 4 should go to index 1 and the one at index 1 should go to index 0, making that cycle complete. So we find these cycles:

0 -> 4 -> 1 (and back to start)
2
3 -> 5 -> 7 -> 6 (and back to start) 

So we have three cycles. Note that the value at index 2 is already at its correct index, and so it is in a cycle of its own.

The first cycle can be executed with the following swaps, starting with the last pair, going backwards:

index 4 <-> index 1
index 0 <-> index 4 

No swap is needed for the value at index 2.

The third cycle can be executed with the following swaps:

index 7 <-> index 6
index 5 <-> index 7
index 3 <-> index 5 

The number of swaps to execute a cycle is its length minus 1.

So in the above example, the number of swaps is (3-1) + (1-1) + (4-1) = 2 + 0 + 3 = 5.