有效地确定置换的奇偶性

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

确定排列是奇数还是奇偶校验的最有效方法是什么？

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

Answer 1

我认为你可以通过简单地计算循环分解在O（n）时间和O（n）空间中做到这一点。

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

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

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

节省空间

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

Answer 2

考虑这种方法……

从排列中，通过交换行并根据顶行顺序进行排序来获得逆置换。 这是O（nlogn）

然后，模拟执行逆置换并计算交换，用于O（n）。 根据这一点，这应该给出排列的奇偶性

可以获得偶数置换作为两个元素的偶数和偶数个交换（称为转置）的组合，而通过（仅）奇数个转置获得奇数置换。

来自维基百科。

这里有一些我曾经躺着的代码，它执行逆置换，我只是修改了一下来计算掉期，你可以删除所有提到的a ， p包含逆置换。

 size_t permute_inverse (std::vector &a, std::vector &p) { size_t cnt = 0 for (size_t i = 0; i < a.size(); ++i) { while (i != p[i]) { ++cnt; std::swap (a[i], a[p[i]]); std::swap (p[i], p[p[i]]); } } return cnt; } 

Answer 3

你想要反转次数的奇偶校验。 您可以使用合并排序在O（n * log n）时间内执行此操作，但要么丢失了初始数组，要么需要额外的内存（O（n））。

一个使用O（n）额外空间的简单算法，是O（n * log n）：

 inv = 0 mergesort A into a copy B for i from 1 to length(A): binary search for position j of A[i] in B remove B[j] from B inv = inv + (j - 1) 

也就是说，我认为不可能在次线性记忆中做到这一点。 也可以看看：

• https://cs.stackexchange.com/questions/3200/counting-inversion-pairs
• https://mathoverflow.net/questions/72669/finding-the-parity-of-a-permutation-in-little-space

Answer 4

我选择Peter de Rivaz作为正确答案的答案，因为这是我最终使用的算法方法。

但是我使用了一些额外的优化，所以我想我会分享它们：

• 首先检查数据的大小
• 如果它大于64，请使用java.util.BitSet存储访问过的元素
• 如果它小于或等于64，则使用long with bitwise操作来存储被访问元素。 这使得O（1）空间适用于仅使用小排列的许多应用程序。
• 实际上返回交换计数而不是奇偶校验。 如果需要，这可以为您提供奇偶校验，但是对于其他目的而言可能是有用的，并且计算起来并不昂贵。

代码如下：

 public int swapCount() { if (length()<=64) { return swapCountSmall(); } else { return swapCountLong(); } } private int swapCountLong() { int n=length(); int swaps=0; BitSet seen=new BitSet(n); for (int i=0; i