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

Question

我想找一种方法来检查两个排列（用列表表示）是否具有相同的奇偶性。需要注意的是，我并不关心它们是偶数还是奇数的奇偶性，只关心它们是否相等。

我刚开始学习Python，我的简单解决方案在下面的回复中给出。我期待着Python高手们能给我一些更优雅、更简洁的代码技巧来实现同样的功能。

Answer 1

这是我对你代码的一些改进建议

• 用list()来复制perm1，这样你就可以把元组等传入函数，让它更通用
• 在for循环中使用enumerate()，而不是len(..)和数组查找，这样代码会更简洁
• 创建一个perm1_map，并保持它的更新，这样可以避免在perm1上进行耗时的O(N)搜索和耗时的列表切片
• 直接返回布尔值，而不是用if ... return True else return False的方式

就是这样

def arePermsEqualParity(perm0, perm1):
    """Check if 2 permutations are of equal parity.

    Assume that both permutation lists are of equal length
    and have the same elements. No need to check for these
    conditions.
    """
    perm1 = list(perm1) ## copy this into a list so we don't mutate the original
    perm1_map = dict((v, i) for i,v in enumerate(perm1))
    transCount = 0
    for loc, p0 in enumerate(perm0):
        p1 = perm1[loc]
        if p0 != p1:
            sloc = perm1_map[p0]                       # Find position in perm1
            perm1[loc], perm1[sloc] = p0, p1           # Swap in perm1
            perm1_map[p0], perm1_map[p1] = sloc, loc   # Swap the map
            transCount += 1
    # Even number of transpositions means equal parity
    return (transCount % 2) == 0

Answer 2

如果我们把两种排列组合在一起，当这两种排列的性质相同时，结果会是偶数性质；如果它们的性质不同，结果就是奇数性质。所以，如果我们解决了性质问题，那么比较两个不同的排列就变得简单了。

性质可以这样判断：随便选一个元素，找到这个元素在排列中被移动到的位置，然后重复这个过程，直到你回到最开始的那个元素。这样你就找到了一个循环：这个排列把所有这些元素都转动了一下。要想把这个循环还原，你需要的交换次数比循环中的元素数量少一个。接着再选一个你还没处理过的元素，重复这个过程，直到你把所有元素都看过。注意，总的来说，你需要的交换次数是每个元素减去每个循环的交换次数。

时间复杂度是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

Answer 3

这是对之前答案的一个小改动 - 复制perm1，并且保存数组查找的结果。

def arePermsEqualParity(perm0, perm1):
    """Check if 2 permutations are of equal parity.

    Assume that both permutation lists are of equal length
    and have the same elements. No need to check for these
    conditions.
    """
    perm1 = perm1[:] ## copy this list so we don't mutate the original

    transCount = 0
    for loc in range(len(perm0) - 1):                         # Do (len - 1) transpositions
        p0 = perm0[loc]
        p1 = perm1[loc]
        if p0 != p1:
            sloc = perm1[loc:].index(p0)+loc          # Find position in perm1
            perm1[loc], perm1[sloc] = p0, p1          # Swap in perm1
            transCount += 1

    # Even number of transpositions means equal parity
    if (transCount % 2) == 0:
        return True
    else:
        return False