¿Cómo comprobar si permutaciones tienen la misma paridad?

Question

Estoy buscando una manera de comprobar si 2 permutaciones (representado por listas) son de la mismo paridad . Tenga en cuenta que no me interesa si son incluso o extraña paridad, sólo la igualdad.

Soy nuevo en Python y mi solución ingenua A continuación se da como respuesta. Estoy mirando adelante a gurús de Python que me muestra algunos trucos para conseguir el mismo código Python en menor medida, más elegante.

Answer 1

Una variante menor de la respuesta anterior - copiar 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

Aquí está mi truco de su código

• Usar 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 bucle en lugar de len (..) y las búsquedas de matriz para el código más limpio
• Haga una perm1_map y mantenerlo al día para detener una costosa O (N) buscar en perm1, y una lista caros rebanada
• devolver el booleano directamente en lugar de la verdadera si ... volver otra cosa 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 3

Si combinamos ambas permutaciones, el resultado tendrá paridad par cuando cada permutación tiene la misma paridad y paridad impar si tienen paridad diferente. Así que si resolvemos el problema de paridad es trivial para 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ó. Usted ha encontrado ahora un ciclo: la permutación gira alrededor de todos estos elementos en una posición. Es necesario un intercambio menor que el número de elementos en el ciclo de deshacerlo. Ahora coge otro elemento que no ha abordado todavía y repetir hasta que haya visto cada elemento. Observa que en total se necesitaba una permuta por elemento de intercambio menos uno por ciclo.

complejidad 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 solamente siempre se puede repetir una vez para cada elemento de 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 4

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 5

Aquí está ligeramente rediseñado de Weeble respuesta :

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

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 7

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 necesarios para ir de uno a otro. Esto a su vez le dará la paridad.

Esto significa que no es necesario hacer las permutas 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 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