How to check if permutations have equal parity?

Question

I am looking for a way to check if 2 permutations (represented by lists) are of the same parity. Note that I am not interested if they are even or odd parity, just the equality.

I am new to Python and my naive solution is given below as a reply. I am looking forward to Python gurus showing me some cool tricks to achieve the same in lesser, more elegant Python code.

Answer 1

My naive solution:

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 2

A minor variant of the previous answer - copy perm1, and save array lookups.

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 3

My intuition tells me that, just counting the differences between the two permutations will give you one more than the number of swaps need to get from one to the other. This in turn will give you the parity.

This means that you don't need to do the swaps in your code at all.

For example:

ABCD, BDCA.

There are three differences, hence two swaps are needed to permute one into the other, hence you have even parity.

Another:

ABCD, CDBA.

There are four differences, hence three swaps, hence odd parity.

Answer 4

Here is my tweak of your code

• Use list() to copy perm1 - this means you can pass tuples, etc into the function, making it more generic
• Use enumerate() in the for loop instead of len(..) and array lookups for neater code
• Make a perm1_map and keep it up to date to stop an expensive O(N) search on perm1, and an expensive list slice
• return the boolean directly rather than the if ... return True else return False

Here is it

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 5

If we combine both permutations, the result will have even parity when each permutation has the same parity, and odd parity if they have different parity. So if we solve the parity problem it's trivial to compare two different permutations.

Parity can be determined as follows: pick an arbitrary element, find the position that the permutation moves this to, repeat until you get back to the one you started with. You have now found a cycle: the permutation rotates all these elements round by one position. You need one swap less than the number of elements in the cycle to undo it. Now pick another element you haven't dealt with yet and repeat until you've seen every element. Observe that in total you needed one swap per element minus one swap per cycle.

Time complexity is O(N) in the size of the permutation. Note that although we have a loop within a loop, the inner loop can only ever iterate once for any element in the permutation.

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])

Also, just for fun, here's a much less efficient but much shorter implementation of the parity function based on the definition in Wikipedia (returning True for even and False for odd):

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 6

Here's slightly refactored 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