algorithm - 如何找到两个不同排列之间的最短交换序列？

Question

我正在寻找某种算法来帮助我解决摆在我面前的任务。我需要找到一种方法来查找(不仅是计数)给定排列中的所有交换(两个元素的交换)，这是将其转换为另一个给定排列所必需的。如果该方法能够找到从一种排列到另一种排列的最小交换次数，那就太好了。有人可以为我提供解决此问题的提示或完整解决方案吗？

Answer 1

首先确定每个值应该放在哪里。然后你会发现移动的周期。以这个数据为例:

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  ) 

然后我们可以得出索引 0 处的值(即 5)应该转到索引 4，索引 4 处的值应该转到索引 1，索引 1 处的值应该转到索引 0，从而形成循环完全的。所以我们找到了这些循环:

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

所以我们有三个周期。请注意，索引 2 处的值已经在其正确的索引处，因此它处于自己的循环中。

第一个循环可以通过以下交换执行，从最后一对开始，向后:

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

索引 2 处的值不需要交换。

第三个循环可以通过以下交换执行:

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

执行一个循环的交换次数是它的长度减去 1。

所以在上面的例子中，交换的次数是(3-1) + (1-1) + (4-1) = 2 + 0 + 3 = 5。