algoritmo para python itertools.permutations

Question

¿Puede alguien explicar el algoritmo para la rutina itertools.permutations en Python standard lib 2.6? No entiendo por qué funciona.

Código es:

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

Es necesario comprender la teoría matemática de permutation cycles, también conocido como "órbitas" (que es importante conocer tanto los "términos de arte" ya que el sujeto matemática, el corazón de combinatorics , es bastante avanzado, y es posible que deba buscar research papers que podría usar uno o ambos términos).

Para una introducción más simple a la teoría de las permutaciones, wikipedia puede ayudar. Cada una de las URL que mencioné ofrece una bibliografía razonable si la combinatoria te fascina lo suficiente como para querer explorar más a fondo y obtener una comprensión real (lo hice personalmente, se convirtió en algo así como un hobby para mí ;-).

Una vez que comprenda la teoría matemática, el código sigue siendo sutil e interesante para "ingeniería inversa". Claramente, indices es sólo la permutación actual en términos de índices en la piscina, ya que los elementos cedidos siempre vienen dadas por

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

Así el corazón de esta maquinaria fascinante es cycles, que representa las órbitas de la permutación y causa indices ser actualizado, en su mayoría por las declaraciones

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

Ie, si cycles[i] es j, esto significa que la próxima actualización de los índices es intercambiar el i-ésimo (desde la izquierda) con el j-ésimo de el derecho (por ejemplo, si j es 1, entonces el último elemento de indices se está intercambiando - indices[-1]). Y luego está la "actualización masiva" menos frecuente cuando un elemento de cycles llegó a 0 durante sus decrementos:

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

Esto pone el i el artículo del th de indices al final, cambiando todos los siguientes artículos de los índices de uno a la izquierda, e indica que la próxima vez que lleguemos a este artículo de cycles estaremos intercambiando el nuevo artículo i de indices (desde la izquierda) con el n - i (desde la derecha) - ese sería el i th una vez más, excepto, por supuesto, por el hecho de que habrá un

cycles[i] -= 1 

antes de examinarlo ;-).

La parte difícil sería, por supuesto, demostrando que esto funciona - es decir, que todas las permutaciones se generan de manera exhaustiva, sin que se solapen y una salida correcta "cronometrado". Creo que, en lugar de una prueba, puede ser más fácil observar cómo funciona la maquinaria cuando está completamente expuesta en casos simples: comentar las declaraciones yield y agregar print (Python 2.*), Tenemos

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) 

La ejecución de esta muestra:

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] 

Enfoque a la cycles: comienzan como 3, 2 - a continuación, el último se reduce, por lo 3, 1 - la el último no es cero todavía así que tenemos un evento "pequeño" (un intercambio en los índices) y rompemos el ciclo interno. Luego ingresamos nuevamente, esta vez la disminución de la última da 3, 0 - la última es ahora cero, por lo que es un evento "grande" - "intercambio masivo" en los índices (bueno, aquí no hay mucha masa, pero, puede haber ;-) y los ciclos han vuelto a 3, 2. Pero ahora no hemos roto el bucle for, por lo que continuamos decrementando el siguiente -to-last (en este caso, el primero) - que da un evento menor, un intercambio en los índices, y rompemos el ciclo interno nuevamente. De vuelta al ciclo, una vez más, el último se decrementa, esta vez dando 2, 1 - evento menor, etc. Eventualmente se produce un bucle completo para solo eventos importantes, no menores, es cuando los ciclos comienzan como todos , por lo que el decremento lleva a cada uno a cero (evento mayor), no se produce yield en ese último ciclo.

Dado que no break se haya ejecutado alguna vez en ese ciclo, tomamos la rama else del for, que devuelve. Tenga en cuenta que el while n puede ser un poco engañoso: en realidad actúa como while True - n nunca cambia, el while loop solo sale de esa declaración return; también podría expresarse como if not n: return seguido de while True:, porque por supuesto cuando n es 0 ("grupo" vacío) no hay nada más que ceder después de la primera y trivial yield vacía. El autor simplemente decidió guardar un par de líneas al colapsar el cheque if not n: con el while ;-).

Le sugiero que continúe con el examen de algunos casos más concretos: finalmente debería percibir el funcionamiento del "mecanismo de relojería". Céntrese en solo cycles al principio (quizás edite las declaraciones print en consecuencia, eliminando indices de ellas), ya que su progreso similar a un mecanismo a través de su órbita es la clave de este algoritmo sutil y profundo; Una vez que grok que, la forma indices obtener correctamente actualizado en respuesta a la secuenciación de cycles es casi un anticlímax -)

Answer 2

Es más fácil de responder con un patrón en los resultados que con las palabras (A menos que usted quiere saber la parte de la matemática de la teoría), así que imprimir sería la mejor manera de explicarlo.
Lo más sutil es que, después de un bucle hasta el final, se reiniciará en el primer giro de la última ronda, y comenzará el siguiente bucle hacia abajo, o reiniciará continuamente al primer giro de la última ronda incluso más grande, como un reloj

La parte del código de hacer el trabajo de reposición:

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

conjunto:

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 

parte del resultado:

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)