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

Question

我正在寻找一种方法来检查 2 排列 （由列表表示）是 相同的 平价. 。请注意，我对它们是否感兴趣不感兴趣 甚至 或者 奇怪的 平等，只是平等。

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

Answer 1

先前答案的一个次要的变体 - 复制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

Answer 2

这是我对你的代码的调整

• 使用 list() 复制 perm1 - 这意味着您可以将元组等传递到函数中，使其更通用
• 在 for 循环中使用 enumerate() 而不是 len(..) 和数组查找以获得更简洁的代码
• 制作一个 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 3

如果我们结合两种置换，其结果将具有偶校验时每个排列具有相同的奇偶性，和奇校验，如果它们具有不同的奇偶性。因此，如果我们解决的平价问题是微不足道的比较两个不同的排列。

奇偶可确定如下：选择一个任意元素，找到位置，该置换移动这，重复，直到你回到你开始使用一个。现在你已经发现了一个循环：置换一个位置旋转，所有这些元素回合。你必须小于周期元素的头号交换撤销它。现在去接你还没有处理另一个元素与尚未和重复，直到你看到的每一个元素。观察到在总你需要每一个元素交换减去每个周期一次交换。

时间复杂度是在置换的尺寸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 4

我的幼稚溶液：

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.
    """

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

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

Answer 5

下面是稍微重构 Weeble的回答 ：

def arePermsEqualParity(perm0, perm1):
    """Whether permutations are of equal parity."""
    return parity(combine(perm0, perm1))

def combine(perm0, perm1):
    """Combine two permutations into one."""
    return map(perm0.__getitem__, perm1)

def parity(permutation):
    """Return even parity for the `permutation`."""
    return (len(permutation) - ncycles(permutation)) % 2 == 0

def ncycles(permutation):
    """Return number of cycles in the `permutation`."""
    ncycles = 0
    seen = [False] * len(permutation)
    for i, already_seen in enumerate(seen):
        if not already_seen:
            ncycles += 1
            # mark indices that belongs to the cycle
            j = i 
            while not seen[j]: 
                seen[j] = True
                j = permutation[j]
    return ncycles

Answer 6

与字典溶液窃听。 这是调试版本：

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] = loc, sloc   # Swap the map
            transCount += 1
    # Even number of transpositions means equal parity
    return (transCount % 2) == 0

唯一的区别是，在词典中的交换未正确地进行。

Answer 7

我的直觉告诉我，只是算两个置换之间的差异会给你一个超过互换的数量需要从一个到另一个获得。这反过来又会给你的奇偶校验。

这意味着你不需要做掉在你的代码在所有。

例如：

ABCD, BDCA.

有三个差异，因此需要两个交换来排列一方转换成另一方，因此你有偶校验。

另：

ABCD, CDBA.

有四个差值，因此3个互换，因此奇校验。

Answer 8

def equalparity(p,q):
    return sum([p[q[i]] > p[q[j]] for i in range(len(p)) for j in range(i)]) % 2 == 0