有效地确定置换的奇偶性 [英] Efficiently determine the parity of a permutation

问题描述

我有一个 int [] 长度为 N 的数组，其中包含值0,1,2，.. ..（N-1），即它表示整数索引的排列。

I have an int[] array of length N containing the values 0, 1, 2, .... (N-1), i.e. it represents a permutation of integer indexes.

确定排列是奇数还是偶数平价？

What's the most efficient way to determine if the permutation has odd or even parity?

（我特别想避免如果可能的话，为临时工作空间分配对象....）

(I'm particularly keen to avoid allocating objects for temporary working space if possible....)

推荐答案

我认为你可以在O（n）时间做到这一点只需计算循环分解即可获得O（n）空间。

I think you can do this in O(n) time and O(n) space by simply computing the cycle decomposition.

您可以通过简单地从第一个元素开始并沿着路径计算O（n）中的循环分解，直到您返回到开始。这为您提供了第一个周期。在跟踪路径时将每个节点标记为已访问。

You can compute the cycle decomposition in O(n) by simply starting with the first element and following the path until you return to the start. This gives you the first cycle. Mark each node as visited as you follow the path.

然后重复下一个未访问的节点，直到所有节点都被标记为已访问。

Then repeat for the next unvisited node until all nodes are marked as visited.

周期的奇偶校验长度k是（k-1）％2，因此您可以简单地将您发现的所有周期的奇偶校验加起来以找到整体排列的奇偶校验。

The parity of a cycle of length k is (k-1)%2, so you can simply add up the parities of all the cycles you have discovered to find the parity of the overall permutation.

将节点标记为已访问的一种方法是在访问时为阵列中的每个值添加N.然后，您可以进行最后整理O（n）传递，将所有数字恢复为原始值。

One way of marking the nodes as visited would be to add N to each value in the array when it is visited. You would then be able to do a final tidying O(n) pass to turn all the numbers back to the original values.

这篇关于有效地确定置换的奇偶性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！