如何找到两个不同排列之间最短的交换顺序?

问题描述 投票:0回答:1

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

algorithm sequence permutation swap
1个回答
0
投票

首先确定每个值应该去哪里。然后,您将找到移动的周期。以这些数据为例:

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。

© www.soinside.com 2019 - 2024. All rights reserved.