¿Cómo comprobar si las permutaciones tienen igual paridad?

Question

Estoy buscando una forma de comprobar si 2 permutaciones (representadas por listas) son del mismas parity. Tenga en cuenta que no estoy interesado si son incluso o paridad impar, solo la igualdad.

Soy nuevo en Python y mi solución ingenua se da a continuación como respuesta. Estoy deseando que los gurús de Python me muestren algunos trucos geniales para lograr lo mismo en un código Python menor y más elegante.

Answer 1

Una variante menor de la respuesta anterior - el ejemplar perm1, y guardar las búsquedas 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

Mi solución ingenua:

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 3

Mi intuición me dice que, simplemente contando las diferencias entre las dos permutaciones le dará uno más que el número de permutas que tenga que ir de uno a otro. Esto a su vez le dará la paridad.

Esto significa que no necesita hacer ningún cambio en su código.

Por ejemplo:

ABCD, BDCA. 

Hay tres diferencias, por lo tanto, se necesitan dos permutas para permutar uno en el otro, por lo tanto, usted tiene paridad par.

Otra:

ABCD, CDBA. 

Hay cuatro diferencias, por lo tanto, tres permutas, por lo tanto, la paridad impar.

Answer 4

Aquí es mi truco de su código

• Uso lista() para copiar perm1 - esto significa que puede pasar tuplas, etc en la función, por lo que es más genérico
• Uso enumerate() en el para bucle en lugar de len (..) y búsquedas de matriz para el código más limpio
• Haga un perm1_map y manténgalo actualizado para detener una costosa búsqueda O (N) en perm1, y un costoso listado
• return the boolean directamente en lugar de si ... return true else return false

Aquí es que

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

Si combinamos ambas permutaciones, el resultado tendrá paridad par cuando cada permutación tiene la misma paridad y paridad impar si tienen paridad diferente. Entonces, si resolvemos el problema de paridad , es trivial comparar dos permutaciones diferentes.

Paridad se puede determinar de la siguiente manera: escoja un elemento arbitrario, encontrar la posición de que la permutación mueve a este, repetir hasta que vuelvas a la que empezó. Ahora ha encontrado un ciclo: la permutación gira todos estos elementos en una posición. Necesitas un intercambio menor que la cantidad de elementos en el ciclo para deshacerlo.Ahora elige otro elemento con el que aún no te hayas ocupado y repite hasta que hayas visto todos los elementos. Observe que, en total, necesitaba un intercambio por elemento menos un intercambio por ciclo.

La complejidad del tiempo es O (N) en el tamaño de la permutación. Tenga en cuenta que aunque tenemos un bucle dentro de un bucle, el bucle interno solo puede iterar una vez para cualquier elemento en la permutació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]) 

Además, sólo por diversión, he aquí una aplicación mucho menos eficiente, pero mucho más corto de la función de la paridad en base a la definición en Wikipedia (volviendo True para uniforme y False para impar):

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

aquí está rediseñado ligeramente 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 

Answer 7

la solución con el diccionario hay micrófonos. Esta es la versión de depuración:

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 

Las únicas diferencias son que el canje en el diccionario no se hizo correctamente.

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