Comment vérifier si les permutations ont parité égale?

Question

Je cherche un moyen de vérifier si 2 permutations (représentés par des listes) sont de même parité . Notez que je ne suis pas intéressé si elles sont même ou impair parité, juste l'égalité.

Je suis nouveau à Python et ma solution naïve est donnée ci-dessous comme réponse. Je suis impatient de gourous Python me montrer quelques trucs cool pour obtenir le même dans le code Python moins, plus élégant.

Answer 1

Une variante mineure de la réponse précédente - copier perm1 et enregistrer du tableau lookups

.

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

Voici mon tweak de votre code

• Liste d'utilisation () pour copier perm1 - cela signifie que vous pouvez passer tuples, etc dans la fonction, ce qui rend plus générique
• Utilisation énumération () dans la boucle à la place de len (..) et les recherches de matrice pour le code plus propre
• un perm1_map et le maintenir à jour pour arrêter un O cher (N) recherche sur perm1, et une tranche de liste cher
• retourner le booléen directement plutôt que si ... retour Vrai Faux sinon retour

est-il ici

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 l'on combine les deux permutations, le résultat aura même la parité lorsque chaque permutation a la même parité et la parité impaire si elles ont la parité différente. Donc, si nous résolvons le problème de parité il est trivial de comparer deux permutations différentes.

Parité peut être déterminée comme suit: choisir un élément arbitraire, trouver la position que la permutation déplace cela, répéter jusqu'à ce que vous revenez à celui que vous avez commencé. Vous avez maintenant trouvé un cycle: la permutation tourne tous ces éléments autour d'une position. Vous avez besoin d'un échange inférieur au nombre d'éléments du cycle pour le défaire. Maintenant, choisissez un autre élément que vous ne l'avez pas encore traité et répéter jusqu'à ce que vous avez vu tous les éléments. Observerez que, au total vous avez besoin d'un swap par élément moins un swap par cycle.

complexité du temps est O (N) à la taille de la permutation. Notez que bien que nous ayons une boucle dans une boucle, la boucle intérieure ne peut jamais itérer une fois pour tout élément dans la 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])

En outre, juste pour le plaisir, voici une beaucoup moins efficace, mais la mise en œuvre beaucoup plus courte de la fonction de parité basée sur la définition dans Wikipedia (retour vrai même pour faux et pour impair):

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

Ma solution naïve:

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

Ici est un peu refondus réponse de Weeble :

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 solution avec le dictionnaire est mis sur écoute. Ceci est la version de débogage:

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

Les seules différences est que le swap dans le dictionnaire n'a pas été fait correctement.

Answer 7

Mon intuition me dit que, ne comptant que les différences entre les deux permutations vous donnera un plus que le nombre de swaps ont besoin pour obtenir de l'un à l'autre. Cela vous donnera la parité.

Cela signifie que vous n'avez pas besoin de faire les swaps dans votre code du tout.

Par exemple:

ABCD, BDCA.

Il existe trois différences, par conséquent, deux swaps sont nécessaires pour permuter un dans l'autre, d'où vous avez même parité.

Une autre:

ABCD, CDBA.

Il y a quatre différences, donc trois swaps, d'où la parité impair.

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