algorithme pour python itertools.permutations

Question

Quelqu'un peut-il expliquer l'algorithme pour la routine itertools.permutations en Python standard lib 2.6? Je ne comprends pas pourquoi ça marche.

code

est:

def permutations(iterable, r=None): 
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 
    # permutations(range(3)) --> 012 021 102 120 201 210 
    pool = tuple(iterable) 
    n = len(pool) 
    r = n if r is None else r 
    if r > n: 
     return 
    indices = range(n) 
    cycles = range(n, n-r, -1) 
    yield tuple(pool[i] for i in indices[:r]) 
    while n: 
     for i in reversed(range(r)): 
      cycles[i] -= 1 
      if cycles[i] == 0: 
       indices[i:] = indices[i+1:] + indices[i:i+1] 
       cycles[i] = n - i 
      else: 
       j = cycles[i] 
       indices[i], indices[-j] = indices[-j], indices[i] 
       yield tuple(pool[i] for i in indices[:r]) 
       break 
     else: 
      return 

Answer 1

Vous devez comprendre la théorie mathématique de permutation cycles, aussi connu comme « orbites » (il est important de connaître les « termes de l'art » puisque le sujet mathématique, le cœur de combinatorics , est assez avancé, et vous devrez peut-être chercher research papers qui pourrait utiliser l'un ou l'autre des termes). Pour une introduction plus simple à la théorie des permutations, wikipedia peut aider. Chacune des URL que j'ai mentionnées offre une bibliographie raisonnable si vous êtes assez fasciné par la combinatoire pour vouloir l'explorer davantage et acquérir une réelle compréhension (je l'ai fait, personnellement - c'est devenu un passe-temps pour moi ;-). Une fois que vous avez compris la théorie mathématique, le code est encore subtil et intéressant à «reverse engineering». De toute évidence, indices est juste la permutation actuelle en termes d'indices dans la piscine, étant donné que les éléments cédés sont toujours donnés par

yield tuple(pool[i] for i in indices[:r]) 

donc au cœur de cette machine fascinante est cycles, qui représente les orbites de la permutation et provoque indices être mis à jour, la plupart du temps par les déclarations

j = cycles[i] 
indices[i], indices[-j] = indices[-j], indices[i] 

Ie, si cycles[i] est j, cela signifie que la prochaine mise à jour des indices est d'échanger le i-ième (à gauche) avec le j-ième de le droit (par exemple, si j est 1, alors le dernier élément de indices est en cours d'échange - indices[-1]). Et puis il y a la « mise à jour en vrac » moins fréquentes lorsqu'un élément de cycles atteint 0 au cours de ses décréments:

indices[i:] = indices[i+1:] + indices[i:i+1] 
cycles[i] = n - i 

ce qui met l'élément i e de indices à la fin, déplacer tous les éléments suivants d'indices un à la à gauche, et indique que la prochaine fois que nous arrivons à cet article de cycles nous allons échanger le nouveau i article de indices (à partir de la gauche) avec le n - i un (de la droite) - ce serait le i e encore une fois, sauf bien sûr pour le fait qu'il y aura un

cycles[i] -= 1 

avant de l'examiner ensuite ;-). La partie difficile serait bien sûr , ce qui prouve que cela fonctionne - c'est-à-dire que toutes les permutations sont générées de manière exhaustive, sans chevauchement et avec une sortie correctement "temporisée". Je pense que, au lieu d'une preuve, il peut être plus facile de regarder comment la machine fonctionne lorsqu'elle est complètement exposée dans des cas simples - en commentant les instructions yield et en ajoutant print (Python 2.*), Nous avons

def permutations(iterable, r=None): 
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 
    # permutations(range(3)) --> 012 021 102 120 201 210 
    pool = tuple(iterable) 
    n = len(pool) 
    r = n if r is None else r 
    if r > n: 
     return 
    indices = range(n) 
    cycles = range(n, n-r, -1) 
    print 'I', 0, cycles, indices 
    # yield tuple(pool[i] for i in indices[:r]) 
    print indices[:r] 
    while n: 
     for i in reversed(range(r)): 
      cycles[i] -= 1 
      if cycles[i] == 0: 
     print 'B', i, cycles, indices 
       indices[i:] = indices[i+1:] + indices[i:i+1] 
       cycles[i] = n - i 
     print 'A', i, cycles, indices 
      else: 
     print 'b', i, cycles, indices 
       j = cycles[i] 
       indices[i], indices[-j] = indices[-j], indices[i] 
     print 'a', i, cycles, indices 
       # yield tuple(pool[i] for i in indices[:r]) 
      print indices[:r] 
       break 
     else: 
      return 

permutations('ABC', 2) 

L'exécution de cette montre:

I 0 [3, 2] [0, 1, 2] 
[0, 1] 
b 1 [3, 1] [0, 1, 2] 
a 1 [3, 1] [0, 2, 1] 
[0, 2] 
B 1 [3, 0] [0, 2, 1] 
A 1 [3, 2] [0, 1, 2] 
b 0 [2, 2] [0, 1, 2] 
a 0 [2, 2] [1, 0, 2] 
[1, 0] 
b 1 [2, 1] [1, 0, 2] 
a 1 [2, 1] [1, 2, 0] 
[1, 2] 
B 1 [2, 0] [1, 2, 0] 
A 1 [2, 2] [1, 0, 2] 
b 0 [1, 2] [1, 0, 2] 
a 0 [1, 2] [2, 0, 1] 
[2, 0] 
b 1 [1, 1] [2, 0, 1] 
a 1 [1, 1] [2, 1, 0] 
[2, 1] 
B 1 [1, 0] [2, 1, 0] 
A 1 [1, 2] [2, 0, 1] 
B 0 [0, 2] [2, 0, 1] 
A 0 [3, 2] [0, 1, 2] 

Mise au point sur la cycles: ils commencent comme 3, 2 - puis le dernier est décrémenté, donc 3, 1 - la le dernier n'est pas encore zéro donc nous avons un "petit" événement (un échange dans les indices) et brisons la boucle interne. Ensuite, nous entrons à nouveau, cette fois le décrément de la dernière donne 3, 0 - le dernier est maintenant zéro, donc c'est un "grand" événement - "échange de masse" dans les indices (bien, il n'y a pas beaucoup de masse ici, mais, il pourrait y avoir ;-) et les cycles sont de retour à 3, 2. Mais maintenant nous n'avons pas rompu la boucle for, donc nous continuons en décrémentant le suivant -to-last (dans ce cas, le premier) - qui donne un événement mineur, un échange dans les indices, et nous cassons la boucle intérieure à nouveau. Retour à la boucle, encore une fois le dernier est décrémenté, cette fois donnant 2, 1 - événement mineur, etc Finalement une boucle entière se produit avec seulement des événements majeurs, pas mineures - c'est quand les cycles commencent comme tous les , donc le décrément prend chacun à zéro (événement majeur), aucun yield se produit sur ce dernier cycle. Jamais break jamais exécuté dans ce cycle, nous prenons la branche else du for, qui revient. Notez que le while n peut être un peu trompeur: il agit en fait comme while True - n ne change jamais, la boucle while sort seulement de cette instruction return; il pourrait également être exprimé comme if not n: return suivi par while True:, parce que bien sûr lorsque n est 0 (vide "pool") il n'y a plus rien à donner après le premier, trivial vide yield. L'auteur a juste décidé de sauvegarder quelques lignes en écrasant le contrôle if not n: avec le while ;-).

Je vous suggère de continuer en examinant un peu plus de cas concrets - finalement vous devriez percevoir le «mouvement d'horloge» fonctionnant. Concentrez-vous sur cycles en premier (peut-être éditez les instructions print en conséquence, en supprimant indices d'eux), puisque leur progression en forme d'horloge à travers leur orbite est la clé de cet algorithme subtil et profond; une fois que vous assimilez que, la façon indices obtenir correctement mis à jour en réponse à la séquence de cycles est presque une anticlimax -)

Answer 2

Il est plus facile de répondre avec un motif dans les résultats que les mots (sauf que vous voulez savoir la partie mathématique de la théorie), ainsi imprime serait la meilleure façon d'expliquer. La chose la plus subtile est que, après avoir fait une boucle à la fin, il se remettrait à zéro au premier tour du dernier tour, et commencerait la prochaine boucle vers le bas, ou reviendrait continuellement au premier tour du dernier rond, même le plus grand. comme une horloge.

La partie du code de faire le travail de remise à zéro:

  if cycles[i] == 0: 
      indices[i:] = indices[i+1:] + indices[i:i+1] 
      cycles[i] = n - i 

tout:

In [54]: def permutations(iterable, r=None): 
    ...:  # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC 
    ...:  # permutations(range(3)) --> 012 021 102 120 201 210 
    ...:  pool = tuple(iterable) 
    ...:  n = len(pool) 
    ...:  r = n if r is None else r 
    ...:  if r > n: 
    ...:   return 
    ...:  indices = range(n) 
    ...:  cycles = range(n, n-r, -1) 
    ...:  yield tuple(pool[i] for i in indices[:r]) 
    ...:  print(indices, cycles) 
    ...:  while n: 
    ...:   for i in reversed(range(r)): 
    ...:    cycles[i] -= 1 
    ...:    if cycles[i] == 0: 
    ...:     indices[i:] = indices[i+1:] + indices[i:i+1] 
    ...:     cycles[i] = n - i 
    ...:     print("reset------------------") 
    ...:     print(indices, cycles) 
    ...:     print("------------------") 
    ...:    else: 
    ...:     j = cycles[i] 
    ...:     indices[i], indices[-j] = indices[-j], indices[i] 
    ...:     print(indices, cycles, i, n-j) 
    ...:     yield tuple(pool[i] for i in indices[:r]) 
    ...:     break 
    ...:   else: 
    ...:    return 

partie du résultat:

In [54]: list(','.join(i) for i in permutations('ABCDE', 3)) 
([0, 1, 2, 3, 4], [5, 4, 3]) 
([0, 1, 3, 2, 4], [5, 4, 2], 2, 3) 
([0, 1, 4, 2, 3], [5, 4, 1], 2, 4) 
reset------------------ 
([0, 1, 2, 3, 4], [5, 4, 3]) 
------------------ 
([0, 2, 1, 3, 4], [5, 3, 3], 1, 2) 
([0, 2, 3, 1, 4], [5, 3, 2], 2, 3) 
([0, 2, 4, 1, 3], [5, 3, 1], 2, 4) 
reset------------------ 
([0, 2, 1, 3, 4], [5, 3, 3]) 
------------------ 
([0, 3, 1, 2, 4], [5, 2, 3], 1, 3) 
([0, 3, 2, 1, 4], [5, 2, 2], 2, 3) 
([0, 3, 4, 1, 2], [5, 2, 1], 2, 4) 
reset------------------ 
([0, 3, 1, 2, 4], [5, 2, 3]) 
------------------ 
([0, 4, 1, 2, 3], [5, 1, 3], 1, 4) 
([0, 4, 2, 1, 3], [5, 1, 2], 2, 3) 
([0, 4, 3, 1, 2], [5, 1, 1], 2, 4) 
reset------------------ 
([0, 4, 1, 2, 3], [5, 1, 3]) 
------------------ 
reset------------------(bigger reset) 
([0, 1, 2, 3, 4], [5, 4, 3]) 
------------------ 
([1, 0, 2, 3, 4], [4, 4, 3], 0, 1) 
([1, 0, 3, 2, 4], [4, 4, 2], 2, 3) 
([1, 0, 4, 2, 3], [4, 4, 1], 2, 4) 
reset------------------ 
([1, 0, 2, 3, 4], [4, 4, 3]) 
------------------ 
([1, 2, 0, 3, 4], [4, 3, 3], 1, 2) 
([1, 2, 3, 0, 4], [4, 3, 2], 2, 3) 
([1, 2, 4, 0, 3], [4, 3, 1], 2, 4)