library - algoritmo para python itertools.permutations

permutation python

Question

¿Alguien puede explicar el algoritmo de la rutina itertools.permutations en la versión 2.6 de Python? No entiendo por qué funciona.

El 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

Debe comprender la teoría matemática de los ciclos de permutación , también conocida como "órbitas" (es importante conocer ambos "términos del arte", ya que el tema matemático, el corazón de la combinatorics , es bastante avanzado, y es posible que deba buscar investigación) documentos que podrían utilizar uno o ambos términos).

Para una introducción más simple a la teoría de permutaciones, wikipedia puede ayudar. Cada una de las URL que mencioné ofrece una bibliografía razonable si te fascinan los combinatorics lo suficiente como para querer explorar más y obtener una comprensión real (lo hice, personalmente, se ha convertido en una especie de hobby para mí ;-).

Una vez que entiendes la teoría matemática, el código aún es sutil e interesante para "ingeniería inversa". Claramente, los indices son solo la permutación actual en términos de índices en el conjunto, dado que los elementos producidos siempre están dados por

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

Así que el corazón de esta fascinante maquinaria son los cycles , que representan las órbitas de la permutación y hacen que los indices se actualicen, principalmente por las declaraciones.

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

Es decir, si los cycles[i] es j , esto significa que la próxima actualización de los índices es intercambiar la i-th one (desde la izquierda) por la j-th one desde la derecha (por ejemplo, si j es 1, entonces el último elemento de los indices está siendo intercambiado - indices[-1] ). Y luego está la "actualización masiva" menos frecuente cuando un ítem de cycles alcanzó 0 durante sus decrementos:

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

esto coloca el ítem de indices al final, desplazando todos los siguientes ítems de índices uno a la izquierda, e indica que la próxima vez que vengamos a este ítem de cycles intercambiaremos el nuevo ítem de indices ( desde la izquierda) con el n - i th one (desde la derecha) - ese sería el i th one otra vez, excepto por supuesto por el hecho de que habrá un

cycles[i] -= 1

antes de que lo examinemos a continuación ;-).

La parte difícil, por supuesto, sería probar que esto funciona, es decir, que todas las permutaciones se generan de manera exhaustiva, sin superposición y una salida "cronometrada" correctamente. Creo que, en lugar de una prueba, puede ser más fácil ver cómo funciona la maquinaria cuando está completamente expuesta en casos simples: comentar las declaraciones de yield y agregar las 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)

Ejecutando esto 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]

Centrarse en los cycles : comienzan como 3, 2; luego, el último disminuye, así que 3, 1: el último aún no es cero, por lo que tenemos un evento "pequeño" (un cambio en los índices) y se rompen el bucle interno Luego ingresamos nuevamente, esta vez la disminución de la última da 3, 0 - la última es ahora cero, así que es un evento "grande" - "intercambio de masa" en los índices (bueno, no hay mucha masa aquí, pero, podría haber ;-) y los ciclos han vuelto a 3, 2. Pero ahora no hemos interrumpido el ciclo for, por lo que continuamos disminuyendo el siguiente al último (en este caso, el primero) - - lo que da un evento menor, un intercambio en los índices, y volvemos a romper el bucle interno. De vuelta al bucle, una vez más, el último se decrementa, esta vez dando 2, 1 - evento menor, etc. Finalmente, se produce un bucle completo con solo eventos mayores, no eventos menores, cuando los ciclos comienzan como todos , por lo que la disminución lleva a cada uno a cero (evento principal), no se produce ningún yield en ese último ciclo.

Como no break ha ejecutado ninguna break en ese ciclo, tomamos la rama else de for , que vuelve. Tenga en cuenta que while n puede ser un poco engañoso: en realidad actúa como un while True - n nunca cambia, el ciclo while solo sale de esa declaración de return ; igualmente podría expresarse como if not n: return seguido por while True: porque, por supuesto, cuando n es 0 ("grupo" vacío) no hay nada más que producir después del primer yield vacío trivial. El autor acaba de decidir guardar un par de líneas al colapsar el if not n: verifique con while ;-).

Le sugiero que continúe examinando algunos casos más concretos; eventualmente debería percibir el funcionamiento del "mecanismo de relojería". Al principio, cycles en los cycles (tal vez edite las declaraciones de print consecuencia, eliminándoles los indices ), ya que su progreso similar a un mecanismo de reloj a través de su órbita es la clave de este algoritmo sutil y profundo; Una vez que asimile eso , ¡la forma en que los indices se actualizan adecuadamente en respuesta a la secuencia de cycles es casi un anticlímax!

Answer 2

Es más fácil responder con un patrón en los resultados que con las palabras (excepto que desea conocer la parte matemática de la teoría), por lo que las impresiones serían la mejor manera de explicar.
Lo más sutil es que, después del bucle hasta el final, se restablecería al primer giro de la última ronda y comenzaría el siguiente bucle hacia abajo, o se reiniciaría continuamente al primer giro de la última ronda aún más grande, como un reloj. .

La parte del código que realiza el trabajo de restablecimiento:

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

todo:

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)