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

如果我们将两种排列组合在一起,当每种排列具有相同的奇偶性时,结果将具有偶数奇偶性,而当它们具有不同的奇偶性时,结果将具有奇数奇偶性。所以如果我们解决了这个问题 奇偶问题 比较两种不同的排列很简单。

对等 可以如下确定:选择任意元素,找到排列移动到的位置,重复,直到回到开始的位置。现在您已经找到了一个循环:排列将所有这些元素旋转一个位置。您需要一次小于循环中元素数的交换才能撤消它。现在,选择另一个尚未处理的元素,并重复,直到看到每个元素为止。请注意,每个元素总共需要一次交换,减去每个周期需要一次交换。

时间复杂度是置换大小的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

• 使用list()复制perm1-这意味着您可以将元组等传递到函数中,使其更通用
• 制作一个perm1_映射并使其保持最新,以停止对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

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

我天真的解决方案:

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

这里有一些轻微的重构 Weeble's answer :

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

这是调试版本:

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

唯一的区别是字典中的交换没有正确进行。

我的直觉告诉我,仅仅计算两种排列之间的差异,就可以得到一种,比从一种排列到另一种排列所需的互换数量还要多。这反过来会给你一个平价。

这意味着您根本不需要在代码中进行交换。

例如:

ABCD, BDCA.

有三种不同,因此需要两种互换将一种互换为另一种互换,因此甚至可以实现平价。

另一个:

ABCD, CDBA.

有四种不同,因此有三种互换,因此有奇数平价。

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