Wie kann man überprüfen, ob Permutationen gleich Parität haben?

Question

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

Ich bin neu in Python und meine naive Lösung ist unten als Antwort gegeben. Ich freue mich auf die Python-Gurus mir ein paar coole Tricks zeigt das gleiche in kleineren, eleganteren 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

Hier ist mein zwicken des Codes

• Verwenden Sie list () kopieren recht1 - dies bedeutet, dass Sie Tupeln, etc. in die Funktion übergeben können, so dass es generische
• Verwendung Aufzählen () in der for-Schleife anstelle von Len (..) und Array-Lookups für sauberere Code
• Erstellen Sie eine perm1_map und halten sie auf dem Laufenden, eine teure O (N) auf recht1 Suche zu stoppen und eine teure Liste Scheibe
• geben die Booleschen direkt anstatt die if ... else return true return false

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 3

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

Parität kann wie folgt ermittelt werden: ein beliebiges Element auswählen, um die Position finden, dass die Permutation bewegt, dies zu wiederholen, bis Sie zum einen wieder mit Ihnen dem Start. Sie haben nun einen Zyklus: die Permutation um eine Position all diese Elemente Runde dreht. Sie benötigen einen Swap kleiner als die Anzahl der Elemente in dem Zyklus sie rückgängig zu machen. Nun ein weiteres Element holen Sie haben nicht noch behandelt und wiederholen, bis Sie jedes Element gesehen haben. Beachten Sie, dass insgesamt Sie benötigt ein Swap pro Element minus ein Swap pro Zyklus.

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

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 basierte (True noch False für ungeradee 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 4

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 5

Hier ist etwas Refactoring Weeble Antwort :

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

Die Lösung mit dem Wörterbuch wird abgehört. 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 besteht darin, dass der Swap im Wörterbuch nicht richtig gemacht wurde.

Answer 7

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

Das bedeutet, dass Sie bei allen Swaps in Ihrem Code nicht tun müssen.

Zum Beispiel:

ABCD, BDCA.

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

Ein anderer:

ABCD, CDBA.

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

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