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

Question

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

3

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

- Kosynier

2个回答

0

目标是将起始排列 S 转换为目标排列 G。正如 tricot 所指出的，目标是在寻找元素“应该在”的位置时，在 S 中生成一系列循环以“解决”这个问题，以便获得 G。这个“解决”步骤可以在线性步数内完成，其大小与每个循环的大小成比例。由于所有循环的长度之和不超过排列的大小 n，因此必须有一个时间复杂度为 O(n) 的算法。实际上，确实有一个算法。但是，在问题的原始表述中，找到这些循环并不容易。

问题的简化版本

为了更容易地找到这些循环，让我们首先考虑我们的问题的一个简化版本，其中目标排列 G 简单地是 1 2 3 ... n。那么，可以很容易地找到每个数字在 S 中所应该处在的位置，因为这些位置可以由数字本身给出。

例中的循环 S = 4 3 2 1 可以很容易地找到，因为只有两个：第一个数字 (4) 应该放在位置 4，而第四个数字 (1) 应该放在位置 1，这使得循环成为 索引 1 -> 索引 4 -> 索引 1。第二个是 索引 2 -> 索引 3 -> 索引 2 (第二个位置的数字 (3) 应该放在位置 3，第三个位置的数字 (2) 应该放在位置 2)。

为了检测循环，我们只需要找到一个位置 i ，使得S [i]！= i（如果S [i] == i ，则我们说在S 中有一个固定点）。请注意，交换S [i]和S [S [i]] 会使S [i] 成为排列中的固定点，因为它被“发送”到其“正确”的位置。解决循环只是使循环中所有数字成为排列中的固定点的过程。在S = 4 3 2 1 中，交换第一个和第四个索引，我们得到S'= 1 3 2 4 。在S = 3 1 2 5 4 中，我们可以通过仅进行两次交换来解决循环1 -> 3 -> 2 -> 1 。

index 1 <-> index 3  ==>  S'  = 2 1 3 5 4
index 1 <-> index 2  ==>  S'' = 1 2 3 5 4

请注意，每次交换都会将循环缩短一个单位。

现在，假设存在一个i，使得S[i]！= i，以下算法解决了一个循环。

while (S[i] != i) {
    swap( S[i], S[S[i]] )
    num_swaps = num_swaps + 1
}

现在解决所有循环问题已经变得非常容易：

function number_of_swaps_simplified(permutation S, permutation G) {
    n = size of G
    num_swaps = 0
    for (i = 0; i < n; ++i) {
        while (S[i] != i) {
            swap( S[i], S[S[i]] )
            num_swaps = num_swaps + 1
        }
    }
    return num_swaps
}

问题的原始版本

我们可以使用上述函数来解决更一般的问题，其中考虑两个任意排列S和G（不用说是相同大小的n）。我们可以通过重新标记G中的数字将其转换为1 2 ... n，并相应地重新标记S中的数字来“归一化”排列。

function normalize(permutation S, permutation G) {
    n = size of G
    map = [0 0 ... 0] // an array of n 0's
    for (i = 0; i < n; ++i) {
        map[G[i]] = i
        G[i] = i
    }
    for (i = 0; i < n; ++i) {
        S[i] = map[S[i]]
    }
    return S, G
}

例如，考虑以下排列及其如何被规范化。

    1 2 3 4 5 6
S = 6 3 4 2 5 1
G = 4 6 1 3 2 5

// map elements of G to get 1 2 3 4 5 6
4 -> 1
6 -> 2
1 -> 3
3 -> 4
2 -> 5
5 -> 6

     1 2 3 4 5 6
S' = 2 4 1 5 6 3
G' = 1 2 3 4 5 6

令S'和G'为归一化排列。显然，G'是1 2 ... n。现在很容易看出，从S到G所需的交换次数与从S'到G'所需的交换次数相同。

function number_of_swaps_general(permutation S, permutation G) {
    // normalize S and G prior to calculating the number of swaps
    S', G' = normalize(S, G)
    return number_of_swaps_simplified(S', G')
}

- Lluís Alemany-Puig

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- trincot · Accepted Answer

首先确定每个值应该放在哪里。然后找到移动的循环。例如，考虑以下数据：

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。