python - 如何检查排列是否具有相等的奇偶性？

Question

我正在寻找一种方法来检查 2 个排列(由列表表示)是否属于相同的 parity 。请注意，我对它们是偶数还是奇数不感兴趣，只关心是否相等。

我是 Python 的新手，下面给出了我天真的解决方案作为答复。我期待着 Python 专家向我展示一些很酷的技巧，以在更简洁、更优雅的 Python 代码中实现相同的目标。

Answer 1

如果我们将两个排列结合起来，当每个排列具有相同的奇偶校验时，结果将具有偶校验，如果它们具有不同的奇偶校验，则结果将具有奇校验。因此，如果我们解决奇偶校验问题，比较两个不同的排列就很简单了。

奇偶性 可以按如下方式确定:选择一个任意元素，找到排列将其移动到的位置，重复直到回到开始的位置。您现在找到了一个循环:排列将所有这些元素旋转一个位置。您需要比循环中的元素数量少一次交换才能撤消它。现在选择另一个您尚未处理的元素并重复，直到您看到每个元素。观察到每个元素总共需要一次交换减去每个循环一次交换。

排列大小的时间复杂度为 O(N)。请注意，虽然我们在循环中有一个循环，但对于排列中的任何元素，内部循环只能迭代一次。

def parity(permutation):
    permutation = list(permutation)
    length = len(permutation)
    elements_seen = [False] * length
    cycles = 0
    for index, already_seen in enumerate(elements_seen):
        if already_seen:
            continue
        cycles += 1
        current = index
        while not elements_seen[current]:
            elements_seen[current] = True
            current = permutation[current]
    return (length-cycles) % 2 == 0

def arePermsEqualParity(perm0, perm1):
    perm0 = list(perm0)
    return parity([perm0[i] for i in perm1])

另外，为了好玩，这里有一个基于维基百科定义的奇偶校验函数的效率低得多但更短的实现(偶数返回 True，奇数返回 False):

def parity(p):
    return sum(
        1 for (x,px) in enumerate(p)
          for (y,py) in enumerate(p)
          if x<y and px>py
        )%2==0