Wie überprüft man, ob die Permutationen die gleiche Parität haben?

Question

Ich bin auf der Suche nach einer Möglichkeit zu überprüfen, ob 2 Permutationen (durch Listen dargestellt) von der gleichen parity sind. Beachten Sie, dass ich nicht interessiert bin, wenn sie sogar oder ungerade Parität sind, nur die Gleichheit.

Ich bin neu bei Python und meine naive Lösung wird unten als Antwort gegeben. Ich freue mich auf Python-Gurus, die mir ein paar coole Tricks zeigen, um dasselbe in weniger elegantem Python-Code zu erreichen.

Answer 1

Eine kleinere Variante der vorherigen Antwort - kopieren recht1 und Array-Lookups speichern.

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

Meine naive Lösung:

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

Meine Intuition sagt mir, dass nur die Unterschiede zwischen den beiden Permutationen zählen wird Ihnen eine mehr als die Zahl der Swaps geben müssen von einem zum anderen gelangen. Dies wird Ihnen wiederum die Parität geben.

Dies bedeutet, dass Sie die Swaps in Ihrem Code überhaupt nicht tun müssen.

Zum Beispiel:

ABCD, BDCA. 

Es gibt drei Unterschiede, also zwei Swaps benötigt werden, einen in die andere permutieren, damit Sie gerade Parität haben.

Ein anderer:

ABCD, CDBA. 

Es gibt vier Unterschiede, also drei Swaps, also ungerade Parität.

Answer 4

Hier ist meine zwicken des Codes

• Verwenden Liste() recht1 kopieren - das bedeutet, dass Sie Tupeln, etc. in die Funktion übergeben können, ist es allgemeinere
• Verwendung enumerate() im Entstehen statt len ​​für Schleife (..) und Array-Lookups für sauberere Code
• ein perm1_map Stellen und halten sie auf dem Laufenden, eine teure O (N) auf recht1 Suche zu stoppen und eine teure Liste Scheibe
• Rückkehr der boolean direkt anstelle des if ... return Wahr sonst return Falsch

Hier ist es

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

Wenn wir beide Permutationen kombinieren, wird das Ergebnis gerade Parität haben, wenn jede Permutation die gleiche Parität hat, und ungerade Parität, wenn sie unterschiedliche Parität haben. Also, wenn wir das Paritätsproblem lösen, ist es trivial, zwei verschiedene Permutationen zu vergleichen.

Parität kann wie folgt bestimmt werden: Wählen Sie ein beliebiges Element, finden Sie die Position, zu der die Permutation dies verschiebt, wiederholen Sie, bis Sie zu demjenigen zurückkommen, mit dem Sie begonnen haben. Sie haben nun einen Zyklus gefunden: Die Permutation dreht alle diese Elemente um eine Position. Sie benötigen einen Swap weniger als die Anzahl der Elemente im Zyklus, um ihn rückgängig zu machen.Wähle nun ein anderes Element aus, mit dem du noch nicht fertig bist, und wiederhole es, bis du jedes Element gesehen hast. Beachten Sie, dass Sie insgesamt einen Tausch pro Element minus einen Tausch pro Zyklus benötigten.

Zeitkomplexität ist O (N) in der Größe der Permutation. Beachten Sie, dass, obwohl wir eine Schleife innerhalb einer Schleife haben, die innere Schleife nur einmal für jedes Element in der Permutation durchlaufen kann.

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

Auch nur zum Spaß, hier ist eine viel weniger effizient, aber viel kürzer Umsetzung der Paritätsfunktion auf der Definition in Wikipedia basiert (für gerade und Falsch für ungerade wahre Rückkehr):

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

hier ist etwas Weeble's answer Refactoring:

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

die Lösung mit dem Wörterbuch abgehört wird. Dies ist die Debug-Version:

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 

Die einzigen Unterschiede bestehen darin, dass der Swap im Wörterbuch nicht richtig gemacht wurde.

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