Come verificare se le permutazioni hanno parità uguale?

Question

Sto cercando un modo per verificare se 2 permessi (rappresentati da elenchi) sono dello stesso parity. Si noti che non sono interessato se sono pari a o dispari pari a, solo l'uguaglianza.

Sono nuovo di Python e la mia soluzione naive è riportata di seguito come risposta. Non vedo l'ora che i guru di Python mi mostrino alcuni trucchi interessanti per ottenere lo stesso risultato in un codice Python minore ed elegante.

Answer 1

Una variante minore della risposta precedente - l'esemplare 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

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 3

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 ti darà la parità.

Ciò significa che non è necessario effettuare lo swap nel codice.

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.

altro:

ABCD, CDBA. 

Esistono quattro differenze, quindi tre swap, parità quindi dispari.

Answer 4

Qui è la mia messa a punto di vostro codice

• Usa lista() per copiare perm1 - questo significa che è possibile passare tuple, ecc nella funzione, il che rende più generico
• Usa enumerate() nella per loop invece di len (..) e ricerca di array per il codice più nuovo
• Crea una perm1_map e mantienila aggiornata per interrompere una costosa ricerca O (N) su perm1, e una costosa lista di liste
• restituisce il valore booleano direttamente piuttosto che il se ... return True else return 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 5

Se uniamo due permutazioni, il risultato avrà parità pari quando ogni permutazione ha la stessa parità e parità dispari se hanno la parità diversa. Quindi, se risolviamo il problema di parità , è banale confrontare due diverse permutazioni.

La parità può essere determinata come segue: selezionare un elemento arbitrario, trovare la posizione in cui la permutazione lo sposta, ripetere fino a tornare a quello con cui si è iniziato. Ora hai trovato un ciclo: la permutazione ruota tutti questi elementi intorno di una posizione. È necessario uno swap in meno del numero di elementi nel ciclo per annullarlo.Ora scegli un altro elemento che non hai ancora affrontato e ripeti finché non hai visto tutti gli elementi. Osserva che in totale hai avuto bisogno di uno swap per elemento meno uno swap per ciclo.

La complessità temporale è O (N) nella dimensione della permutazione. Notare che sebbene abbiamo un ciclo all'interno di un ciclo, il ciclo interno può sempre iterare una sola volta per qualsiasi 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 6

Ecco un po 'refactoring 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 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 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