有效确定排列的奇偶性

Question

我有一个长度为

int[]

的

N

数组，其中包含值 0, 1, 2, .... (N-1)，即它表示整数索引的排列。

确定排列是否具有奇数或偶数奇偶性的最有效方法是什么？

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

Answer 1

我认为你可以通过简单地计算循环分解来在 O(n) 时间和 O(n) 空间中完成此操作。

您可以通过简单地从第一个元素开始并沿着路径直到返回起点来计算 O(n) 的循环分解。 这给了你第一个周期。 当您沿着路径前进时，将每个节点标记为已访问。

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

长度为 k 的循环的奇偶校验为 (k-1)%2，因此您只需将发现的所有循环的奇偶校验相加即可找到整体排列的奇偶校验。

节省空间

将节点标记为已访问的一种方法是在访问数组时将 N 添加到数组中的每个值。 然后，您可以进行最终的整理 O(n) 遍，将所有数字恢复为原始值。

Answer 2

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

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

• 先检查数据大小
• 如果大于64，则使用

  java.util.BitSet

  来存储访问过的元素
• 如果小于等于64，则使用long加按位运算来存储访问过的元素。这使得许多仅使用小排列的应用程序的空间为 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<n; i++) {
        if (seen.get(i)) continue;
        seen.set(i);
        for(int j=data[i]; !seen.get(j); j=data[j]) {
            seen.set(j);
            swaps++;
        }       
    }
    return swaps;
}

private int swapCountSmall() {
    int n=length();
    int swaps=0;
    long seen=0;
    for (int i=0; i<n; i++) {
        long mask=(1L<<i);
        if ((seen&mask)!=0) continue;
        seen|=mask;
        for(int j=data[i]; (seen&(1L<<j))==0; j=data[j]) {
            seen|=(1L<<j);
            swaps++;
        }       
    }
    return swaps;
}

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

考虑这种方法...

从排列中，通过交换行和得到逆排列 根据顶行顺序排序。这是 O(nlogn)

然后，模拟执行逆排列并计算交换次数，时间复杂度为 O(n)。根据这个

，这应该给出排列的奇偶性

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

来自维基百科。

这是我手头上的一些代码，它执行逆排列，我只是对其进行了一些修改以计算交换，您可以删除所有提到的

a

，

p

包含逆排列。

size_t
permute_inverse (std::vector<int> &a, std::vector<size_t> &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 5

只是警告 Peter de Rivaz 的答案不正确。奇偶校验不是由周期长度定义的。考虑具有相同长度但奇偶性不同的循环 (123) 和 (132)