排列中的交换次数

Question

是否有一种有效的算法(在大O表示法方面有效)来找到交换数量以将置换P转换为身份置换I？交换不需要在相邻元素上,而是在任何元素上.

例如:

I = {0, 1, 2, 3, 4, 5}, number of swaps is 0
P = {0, 1, 5, 3, 4, 2}, number of swaps is 1 (2 and 5)
P = {4, 1, 3, 5, 0, 2}, number of swaps is 3 (2 with 5, 3 with 5, 4 with 0)

一个想法是编写这样的算法:

int count = 0;
for(int i = 0; i < n; ++ i) {
    for(; P[i] != i; ++ count) { // could be permuted multiple times
        std::swap(P[P[i]], P[i]);
        // look where the number at hand should be
    }
}

但我不清楚这是否真的可以保证终止或者是否找到了正确的掉期数量.它适用于上面的例子.我尝试在5个和12个数字上生成所有排列,它总是终止于那些.

这个问题出现在数值线性代数中.一些矩阵分解使用旋转,其有效地交换行以具有用于操纵的下一行的最大值,以避免被小数除法并提高数值稳定性.一些分解,例如LU分解可以稍后用于计算矩阵行列式,但是如果排列的数量是奇数,则分解的行列式的符号与原始矩阵的符号相反.

编辑:我同意这个问题类似于计算将一个排列转换为另一个排列所需的相邻交换.但我认为这个问题更为根本.通过在O(n)中反转目标置换,组成O(n)中的置换,然后从那里找到交换的数量到身份,可以将置换从一个转换为另一个.通过明确地将身份表示为另一种排列来解决这个问题似乎不是最理想的.此外,直到昨天,另一个问题是四个答案,其中只有一个答案(通过|\/ | ad)似乎有用,但该方法的描述似乎含糊不清.现在用户lizusek在那里提供了我的问题的答案.我不同意将此问题视为重复.

编辑2:提出的算法实际上似乎是相当优化的,正如用户rcgldr的评论所指出的,请参阅我的答案,计算将一个排列转换为另一个排列所需的相邻交换.

Answer 1

我相信关键是要根据循环分解来考虑置换。

这表示任何排列都是不相交的循环的产物。

关键事实是：

1. 在两个不连续的周期中交换元素会产生一个更长的周期
2. 在同一周期内交换元素会减少一个周期
3. 所需的排列数为nc，其中c是分解中的循环数

您的算法始终在同一周期内交换元素，因此将正确计算所需的交换次数。

如果需要，还可以通过计算周期分解并返回n减去找到的周期数，在O（n）中执行此操作。

循环分解的计算可以在O（n）中完成，方法是从第一个节点开始，然后进行排列直到再次到达起点。标记所有访问的节点，然后从下一个未访问的节点重新开始。