Comment vérifier si les permutations ont la même parité?

Question

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

Je suis nouveau à Python et ma solution naïve est donnée ci-dessous comme réponse. J'attends avec impatience les gourous Python qui me montreront quelques trucs sympas pour réaliser la même chose dans un code Python moins élégant.

Answer 1

Une variante mineure de la réponse précédente - copie 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

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 3

Mon intuition me dit que, ne comptant que les différences entre les deux permutations vous donnera un plus que le nombre de swaps doivent passer d'une à l'autre. Cela vous donnera la parité. Cela signifie que vous n'avez pas du tout besoin d'effectuer les swaps dans votre code.

Par exemple:

ABCD, BDCA. 

Il y a trois différences, il faut donc deux swaps permutant l'un dans l'autre, d'où vous avez même parité.

autre:

ABCD, CDBA. 

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

Answer 4

Voici mon tweak de votre code

• liste Utilisation() pour copier perm1 - cela signifie que vous pouvez passer tuples, etc dans la fonction, ce qui rend
plus générique
• Utilisez enumerate() dans la pour la boucle au lieu de len (..) et les recherches de tableau pour le code plus propre
• Faire un perm1_map et le garder à jour pour arrêter un O cher (N) recherche sur perm1, et une liste coûteuse tranche
• retour booléen directement plutôt que le si ... retour Vrai sinon retour Faux

Voici ce

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

Si nous combinons 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.

La parité peut être déterminée comme suit: choisissez un élément quelconque, trouvez la position à laquelle la permutation se déplace, répétez jusqu'à ce que vous reveniez à celui avec lequel vous avez commencé. Vous avez maintenant trouvé un cycle: la permutation fait tourner tous ces éléments autour d'une position. Vous avez besoin d'un swap inférieur au nombre d'éléments du cycle pour l'annuler.Maintenant, choisissez un autre élément que vous n'avez pas encore traité et répétez jusqu'à ce que vous ayez vu tous les éléments. Observez qu'au total, vous avez besoin d'un échange par élément moins un échange par cycle.

La complexité temporelle est O (N) dans la taille de la permutation. Notez que bien que nous ayons une boucle dans une boucle, la boucle interne peut seulement itérer une fois pour n'importe quel élément de 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]) 

Aussi, juste pour le plaisir, voici une mise en œuvre beaucoup moins efficace mais beaucoup plus courte de la fonction de parité basée sur la définition dans Wikipedia (retour vrai même pour et faux 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 6

ici est un peu refondus 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 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 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