Je cherche un moyen de vérifier si 2 Je suis nouveau à Python et ma solution naïve est donnée ci-dessous en réponse. J'attends avec impatience Python Gurus me montrant des astuces fraîches pour obtenir la même chose en code Python moindre et plus élégant.
8 Réponses :
Ma solution naïve:
La seule amélioration que je peux voir est que la recherche Perm1.index (Perm0 [LOC]) ne doit réellement vérifier Perm1 après LOC - Je ne sais pas comment exprimer cela efficacement en Python.
Je suppose que nous voudrions peut-être copier Perm1 afin que l'opération ne mute pas l'argument Perm1?
Douglas: Vous avez raison de faire une copie de Perm1. Je n'étais même pas conscient que les listes sont transmises par référence aux fonctions (et donc modifiables dans)!
une variante mineure de la réponse précédente - Copie Perm1 et sauvegardez les recherches de tableau.
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
Mon intuition me dit que, en comptant simplement les différences entre les deux permutations vous donnera un de plus que le nombre de swaps nécessaires pour obtenir de l'une à l'autre. Cela vous donnera à son tour la parité.
Cela signifie que vous n'avez pas besoin de faire les swaps de votre code du tout. P>
Par exemple: P>
ABCD, CDBA.
Badc - 4 Différences - Seulement 2 swaps nécessaires.
Contre-échantillon: ABCD, BADC. Il y a quatre différences, mais seulement deux swaps. (Swap AB, Swap CD.) Je pense que la parité dépend du nombre de cycles.
Oups, on dirait que j'étais un peu en retard avec ça!
Et c'est pourquoi l'intuition est nulle. Laissez la raison prévaloir!
Voici mon modification de votre code
Voici IT P>
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
Si nous combinons les deux permutations, le résultat aura même une parité lorsque chaque permutation a la même parité et la même parité si elles ont une parité différente. Donc, si nous résolvons le problème de la parité Parité forte> peut être déterminé comme suit: Choisissez un élément arbitraire, trouvez la position que la permutation Déplace cela pour répéter jusqu'à ce que vous reveniez à celui que vous avez commencé. Vous avez maintenant trouvé un cycle: la permutation fait pivoter tous ces éléments autour d'une position. Vous avez besoin d'un échange de moins que le 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été 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. P> La complexité de temps est O (n) de la taille de la permutation. Notez que bien que nous ayons une boucle au sein d'une boucle, la boucle interne ne peut jamais parcourir une seule fois pour tout élément de la permutation. P> 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
[P0 [P1 [I]] Pour i In Xrange (LEN (P0))] -> [P0 [I] pour I in P1] ?
Hehe, c'est tellement évident maintenant que vous le soulignez! Je vais éditer ceux-ci.
Merci beaucoup d'avoir souligné cette approche alternative! Il devient d'autant plus optimal (et utile) pour un scénario où Perm0 reste constant et comparé à de nombreuses listes Perm1.
voici légèrement refactored 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
La solution avec le dictionnaire est bogu.
Ceci est la version de débogage: Les seules différences sont que l'échange dans le dictionnaire n'a pas été effectué correctement.
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
Une permutation est-elle une liste de cycles disjoints? Une liste de paires de transposition? Une liste de
(s, σ (s)) paires (où σ est la permutation à être représentée)?Outis: Je suppose que cela peut être les deux.