如何检查排列是否具有相等的平价？

Question

我正在寻找一种方法来检查2 个排列(由列表表示)是否具有相同的奇偶校验.请注意,如果它们是偶数或奇数奇偶校验,我就不感兴趣,只是相等.

我是Python新手,我的天真解决方案在下面作为回复给出.我期待Python专家向我展示一些很酷的技巧,以便在更小,更优雅的Python代码中实现相同的功能.

Answer 1

这是我对你的代码的调整

• 使用list()复制perm1 - 这意味着您可以将元组等传递给函数,使其更通用
• 在for循环中使用enumerate()而不是len(..),并在neater代码中使用数组查找
• 创建一个perm1_map并使其保持最新以停止对perm1进行昂贵的O(N)搜索,以及一个昂贵的列表切片
• 直接返回布尔值而不是if ...返回True否则返回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])

另外,只是为了好玩,这是基于Wikipedia中定义的奇偶校验函数的效率低得多但更短的实现(对于偶数返回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