Como verificar se permutações têm igual paridade?

Question

Eu estou procurando uma maneira de verificar se 2 permutações (representado por listas) são da mesma paridade . Note que não estou interessado se eles são até ou estranho paridade, apenas a igualdade.

Eu sou novo para Python e minha solução ingênua é dado abaixo como resposta. Estou ansioso para gurus Python mostrando-me alguns truques para conseguir o mesmo em menor código Python, mais elegante.

Answer 1

A variante menor da resposta anterior -. Cópia perm1 e salvar pesquisas de matriz

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

Aqui está o meu puxão de seu código

• Use list () para copiar perm1 - Isso significa que você pode passar tuplas, etc para a função, tornando-o mais genérico
• Uso enumerar () no loop for em vez de pesquisas de len (..) e da matriz de código mais puro
• Faça um perm1_map e mantê-lo atualizado para parar um O caro (N) Procurar no perm1 e uma fatia lista caro
• retornar o booleano diretamente em vez de o se ... return true else return false

Aqui está ele

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

Se combinarmos as duas permutações, o resultado terá ainda a paridade quando cada permutação tem a mesma paridade e paridade ímpar se eles têm paridade diferente. Então, se nós resolver o problema paridade é trivial para comparar duas permutações diferentes.

Paridade pode ser determinada da seguinte forma: pegar um elemento arbitrário, encontrar a posição de que a permutação move isso, repita até você voltar ao que você começou com. Você já encontrou um ciclo: a rotação de permutação todos estes elementos redondos por uma posição. Você precisa de um swap de menos do que o número de elementos no ciclo de desfazê-lo. Agora pegue um outro elemento que não têm lidado com ainda e repetir até que você tenha visto a cada elemento. Observe-se que, no total, você precisava de uma troca por elemento menos uma troca por ciclo.

complexidade

O tempo é S (N) no tamanho da permutação. Note-se que embora tenhamos um loop dentro de um loop, o loop interno pode sempre apenas iterate uma vez para qualquer elemento da permutação.

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

Além disso, apenas por diversão, aqui é uma implementação muito menos eficiente, mas muito mais curto da função de paridade com base na definição na Wikipedia (retornando True para uniforme e False para ímpar):

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

A minha solução ingênua:

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

Aqui está ligeiramente reformulado de Weeble resposta :

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

A solução com o dicionário está grampeada. Esta é a versão de depuração:

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

As únicas diferenças é que a troca no dicionário não foi feito corretamente.

Answer 7

Minha intuição me diz que, contando apenas as diferenças entre as duas permutações lhe dará um a mais que o número de swaps precisa ir de um para o outro. Este, por sua vez, irá dar-lhe a paridade.

Isto significa que você não precisa fazer os swaps em seu código em tudo.

Por exemplo:

ABCD, BDCA.

Há três diferenças, portanto, dois swaps são necessários para permutar um para o outro, portanto, você tem paridade par.

Outra:

ABCD, CDBA.

Há quatro diferenças, daí três swaps, paridade, portanto, estranho.

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