Come controllare se permutazioni hanno pari parità?

Question

Sto cercando un modo per verificare se 2 permutazioni (rappresentata da liste) sono del stesso parità . Si noti che non mi interessa se sono anche o dispari di parità, solo l'uguaglianza.

Sono nuovo di Python e la mia soluzione ingenua è riportata qui sotto come una risposta. Non vedo l'ora di guru Python mi mostra alcuni trucchetti per ottenere lo stesso in minore, più elegante codice Python.

Answer 1

Una variante minore del precedente risposta - copiare perm1, e salvare le ricerche di matrice

.

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

Ecco la mia ritocco del vostro codice

• Usa elenco () per copiare perm1 - questo significa che è possibile passare tuple, ecc nella funzione, il che rende più generico
• Usa enumerate () nel ciclo for, invece di len (..) e le ricerche di matrice per il codice più ordinato
• Fare un perm1_map e tenerlo aggiornato per fermare un O costoso (N) cercare perm1, e una lista fetta costosa
• restituire il valore booleano direttamente piuttosto che il se ... tornare Vero altro ritorno False

Ecco che

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 uniamo due permutazioni, il risultato avrà parità pari quando ogni permutazione ha la stessa parità, parità dispari e se hanno la parità diversa. Quindi, se si risolve il problema di parità è banale per confrontare due permutazioni differenti.

Parità può essere determinata come segue: scegliere un elemento arbitrario, trovare la posizione che la permutazione si muove questo, ripetere fino a tornare a quello di partenza. Hai trovato un ciclo: la permutazione ruota tutti questi elementi giro di una posizione. Avete bisogno di uno scambio meno il numero di elementi nel ciclo per annullarla. Ora scegliere un altro elemento che non hai ancora affrontato e ripetere fino a quando hai visto ogni elemento. Si osservi che in totale avevi bisogno di uno scambio per elemento meno uno scambio per ciclo.

Il tempo è la complessità O (N) nella dimensione della permutazione. Si noti che anche se abbiamo un ciclo all'interno di un ciclo, il ciclo interno può sempre e solo iterare una volta per ogni elemento nella permutazione.

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

Inoltre, solo per divertimento, ecco un'implementazione molto meno efficiente, ma molto più breve della funzione di parità in base alla definizione di Wikipedia (ritorno vero anche per e False per dispari):

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

La mia soluzione 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

Ecco un po 'refactoring di Weeble risposta :

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 soluzione con il dizionario è sempre sotto controllo. Questa è la versione di debug:

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

Le uniche differenze sono che lo swap nel dizionario non è stato fatto correttamente.

Answer 7

Il mio intuito mi dice che, solo contando le differenze tra i due permutazioni vi darà uno in più del numero di swap bisogno di ottenere da uno all'altro. Questo a sua volta vi darà la parità.

Questo significa che non è necessario fare swap nel codice a tutti.

Ad esempio:

ABCD, BDCA.

Ci sono tre differenze, quindi due swap sono necessari per permutare l'uno nell'altro, e quindi si ha parità pari.

Un altro:

ABCD, CDBA.

Ci sono quattro differenze, quindi tre swap, quindi la parità dispari.

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