Algoritmo de Steinhaus-Johnson-Trotter

El ciclo hamiltoniano en el gráfico de Cayley del grupo simétrico generado por el algoritmo Steinhaus-Johnson-Trotter

Diagrama de rueda de todas las permutaciones de longitud generadas por el algoritmo Steinhaus-Johnson-Trotter, donde cada permutación está codificada por colores (1=azul, 2=verde, 3=amarillo, 4=rojo). ${\displaystyle n=4}$

El algoritmo Steinhaus-Johnson-Trotter o algoritmo de Johnson-Trotter , también llamado cambios simples , es un algoritmo que lleva el nombre de Hugo Steinhaus , Selmer M. Johnson y Hale F. Trotter que genera todas las permutaciones de elementos. Cada dos permutaciones adyacentes en la secuencia resultante difieren al intercambiar dos elementos permutados adyacentes. De manera equivalente, este algoritmo encuentra un ciclo hamiltoniano en el permutoedro , un politopo cuyos vértices representan permutaciones y cuyas aristas representan intercambios. ${\displaystyle n}$

Este método ya era conocido por los cambiadores ingleses del siglo XVII , y Robert Sedgewick lo llama "quizás el algoritmo de enumeración de permutaciones más destacado". ^[1] Se puede implementar una versión del algoritmo de tal manera que el tiempo promedio por permutación sea constante. Además de ser simple y computacionalmente eficiente, este algoritmo tiene la ventaja de que los cálculos posteriores sobre las permutaciones generadas pueden acelerarse aprovechando la similitud entre permutaciones consecutivas. ^[1]

Algoritmo

La secuencia de permutaciones generada por el algoritmo Steinhaus-Johnson-Trotter tiene una estructura recursiva natural , que puede generarse mediante un algoritmo recursivo. Sin embargo, el algoritmo Steinhaus-Johnson-Trotter real no utiliza recursividad, sino que calcula la misma secuencia de permutaciones mediante un método iterativo simple. Una mejora posterior le permite ejecutarse en un tiempo promedio constante por permutación.

Estructura recursiva

La secuencia de permutaciones para un número dado se puede formar a partir de la secuencia de permutaciones colocando el número en cada posición posible en cada una de las permutaciones más cortas. El algoritmo Steinhaus-Johnson-Trotter sigue esta estructura: la secuencia de permutaciones que genera consta de bloques de permutaciones, de modo que dentro de cada bloque las permutaciones coinciden en el orden de los números del 1 al y difieren sólo en la posición de . Los bloques en sí están ordenados de forma recursiva, según el algoritmo Steinhaus-Johnson-Trotter para un elemento menos. Dentro de cada bloque, las posiciones en las que se coloca ocurren en orden descendente o ascendente, y los bloques alternan entre estos dos órdenes: las ubicaciones en el primer bloque son en orden descendente, en el segundo bloque están en orden ascendente, en el tercer bloque están en orden descendente, y así sucesivamente. ^[2] ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle (n-1)!}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Así, a partir de la única permutación de un elemento,

1

se puede colocar el número 2 en cada posición posible en orden descendente para formar una lista de dos permutaciones en dos elementos,

1 2

2 1

Luego, se puede colocar el número 3 en cada una de tres posiciones diferentes para estas dos permutaciones, en orden descendente para la primera permutación 1 2, y luego en orden ascendente para la permutación 2 1:

1 2 3

1 3 2

3 1 2

3 2 1

2 3 1

2 1 3

El mismo patrón de ubicación, alternando entre ubicaciones descendentes y ascendentes de , se aplica a cualquier valor mayor de . ^[2] En secuencias de permutaciones con esta estructura recursiva, cada permutación difiere de la anterior ya sea por el movimiento de una sola posición a la vez o por un cambio de dos números más pequeños heredados de la secuencia anterior de permutaciones más cortas. . En cualquier caso, esta diferencia es sólo la transposición de dos elementos adyacentes. Cuando el primer y último elemento de la sucesión, además, difieren sólo en dos elementos adyacentes (las posiciones de los números y ), como puede comprobarse por inducción. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n>1}$ ${\displaystyle 1}$ ${\displaystyle 2}$

Esta secuencia puede generarse mediante un algoritmo recursivo que construye la secuencia de permutaciones más pequeñas y luego realiza todas las inserciones posibles del número más grande en la secuencia generada recursivamente. ^[2] El mismo orden de permutaciones también se puede describir de manera equivalente como el orden generado por el siguiente algoritmo codicioso. ^[3] Comience con la permutación de identidad . Ahora transponga repetidamente la entrada más grande posible con la entrada a su izquierda o derecha, de modo que en cada paso, se cree una nueva permutación que no se haya encontrado antes en la lista de permutaciones. Por ejemplo, en el caso de que la secuencia comience con , luego voltea con su vecino izquierdo para obtener . A partir de este punto, invertir con su vecino derecho produciría la permutación inicial , por lo que la secuencia cambia con su vecino izquierdo y llega a , etc. La dirección de la transposición (izquierda o derecha) siempre está determinada de forma única en este algoritmo. Sin embargo, el algoritmo Steinhaus-Johnson-Trotter real no utiliza recursividad y no necesita realizar un seguimiento de las permutaciones que ya ha encontrado. En cambio, calcula la misma secuencia de permutaciones mediante un método iterativo simple . ${\displaystyle 1\;2\;\ldots \;n}$ ${\displaystyle n=3}$ ${\displaystyle 1\;2\;3}$ ${\displaystyle 3}$ ${\displaystyle 1\;3\;2}$ ${\displaystyle 3}$ ${\displaystyle 2}$ ${\displaystyle 1\;2\;3}$ ${\displaystyle 3}$ ${\displaystyle 1}$ ${\displaystyle 3\;1\;2}$

Versión original

Como lo describe Johnson, el algoritmo para generar la siguiente permutación a partir de una permutación dada realiza los siguientes pasos. ${\displaystyle \pi }$

• Para cada uno de 1 a , sea la posición donde se coloca el valor en la permutación . Si el orden de los números del 1 al in permutación define una permutación par , de lo contrario, dejemos . ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$ ${\displaystyle \pi }$ ${\displaystyle i-1}$ ${\displaystyle \pi }$ ${\displaystyle y_{i}=x_{i}-1}$ ${\displaystyle y_{i}=x_{i}+1}$
• Encuentre el número más grande para el cual define una posición válida en la permutación que contiene un número menor que . Intercambie los valores en posiciones y . ${\displaystyle i}$ ${\displaystyle y_{i}}$ ${\displaystyle \pi }$ ${\displaystyle i}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$

Cuando no se puede encontrar ningún número que cumpla las condiciones del segundo paso del algoritmo, el algoritmo ha alcanzado la permutación final de la secuencia y termina. Este procedimiento podrá implementarse en el tiempo por permutación. ^[4] ${\displaystyle i}$ ${\displaystyle O(n)}$

Trotter ofrece una implementación alternativa de un algoritmo iterativo para la misma secuencia, en notación ALGOL 60 ligeramente comentada. ^[5]

Debido a que este método genera permutaciones que alternan entre pares e impares, se puede modificar fácilmente para generar solo las permutaciones pares o solo las impares: para generar la siguiente permutación de la misma paridad a partir de una permutación dada, simplemente aplique el mismo procedimiento dos veces. . ^[6]

La aceleración de Even

Una mejora posterior realizada por Shimon Even proporciona una mejora en el tiempo de ejecución del algoritmo al almacenar información adicional para cada elemento en la permutación: su posición y una dirección (positiva, negativa o cero) en la que se está moviendo actualmente (esencialmente, esta es la misma información calculada usando la paridad de la permutación en la versión del algoritmo de Johnson). Inicialmente, la dirección del número 1 es cero y todos los demás elementos tienen una dirección negativa:

1-2-3

En cada paso, el algoritmo encuentra el elemento más grande con una dirección distinta de cero y lo intercambia en la dirección indicada:

1-3-2

Si esto hace que el elemento elegido alcance la primera o última posición dentro de la permutación, o si el siguiente elemento en la misma dirección es mayor que el elemento elegido, la dirección del elemento elegido se establece en cero:

3 1 −2

Después de cada paso, todos los elementos mayores que el elemento elegido (que anteriormente tenía dirección cero) tienen sus direcciones configuradas para indicar movimiento hacia el elemento elegido. Es decir, positivo para todos los elementos entre el inicio de la permutación y el elemento elegido, y negativo para los elementos hacia el final. Así, en este ejemplo, después de que el número 2 se mueve, el número 3 vuelve a estar marcado con una dirección:

+3 2 1

Los dos pasos restantes del algoritmo son: ${\displaystyle n=3}$

2 +3 1

2 1 3

Cuando todos los números quedan sin marcar, el algoritmo finaliza. ^[7]

Este algoritmo toma tiempo para cada paso en el que se encuentre el mayor número a mover . Por lo tanto, los intercambios que involucran el número toman sólo un tiempo constante; Dado que estos intercambios representan todos menos una fracción de todos los intercambios realizados por el algoritmo, el tiempo promedio por permutación generada también es constante, aunque una pequeña cantidad de permutaciones tomará una mayor cantidad de tiempo. ^[1] ${\displaystyle O(i)}$ ${\displaystyle n-i+1}$ ${\displaystyle n}$ ${\displaystyle 1/n}$

Una versión sin bucles más compleja del mismo procedimiento adecuada para la programación funcional permite realizarlo en tiempo constante por permutación en todos los casos; sin embargo, las modificaciones necesarias para eliminar los bucles del procedimiento lo hacen más lento en la práctica. ^[8]

Estructuras relacionadas

permutoedro

El conjunto de todas las permutaciones de elementos puede representarse geométricamente mediante un permutoedro , el politopo formado a partir de la cáscara convexa de los vectores, las permutaciones del vector . Aunque se define de esta manera en un espacio de dimensiones, en realidad es un politopo de dimensiones; por ejemplo, el permutoedro de cuatro elementos es un poliedro tridimensional, el octaedro truncado . Si cada vértice del permutoedro está etiquetado por la permutación inversa a la permutación definida por sus coordenadas de vértice, el etiquetado resultante describe un gráfico de Cayley del grupo simétrico de permutaciones en elementos, generado por las permutaciones que intercambian pares de elementos adyacentes. Así, cada dos permutaciones consecutivas en la secuencia generada por el algoritmo Steinhaus-Johnson-Trotter corresponden de esta manera a dos vértices que forman los puntos finales de una arista en el permutoedro, y toda la secuencia de permutaciones describe un camino hamiltoniano en el permutoedro, un camino que pasa por cada vértice exactamente una vez. Si la secuencia de permutaciones se completa agregando una arista más de la última permutación a la primera de la secuencia, el resultado es un ciclo hamiltoniano. ^[9] ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle (1,2,\dots n)}$ ${\displaystyle n}$ ${\displaystyle (n-1)}$ ${\displaystyle n}$

Códigos grises

Un código Gray para números en una base dada es una secuencia que contiene cada número hasta un límite dado exactamente una vez, de tal manera que cada par de números consecutivos difiere en uno en un solo dígito. Las permutaciones de los números del 1 al se pueden colocar en correspondencia uno a uno con los números del 0 al emparejando cada permutación con la secuencia de números que cuenta el número de posiciones en la permutación que están a la derecha del valor y que contienen un valor menor que (es decir, el número de inversiones para las cuales es el mayor de los dos valores invertidos), y luego interpretar estas secuencias como números en el sistema numérico factorial , es decir, el sistema de bases mixtas con secuencia de bases para Por ejemplo, la permutación daría los valores , , , y . La secuencia de estos valores, da el número. Las permutaciones consecutivas en la secuencia generada por el algoritmo Steinhaus-Johnson-Trotter tienen números de inversiones que difieren en uno, formando un código de Gray para el sistema numérico factorial. ^[10] ${\displaystyle n!}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle n!-1}$ ${\displaystyle c_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle (1,2,3,4,\dots )}$ ${\displaystyle (3,1,4,5,2)}$ ${\displaystyle c_{1}=0}$ ${\displaystyle c_{2}=0}$ ${\displaystyle c_{3}=2}$ ${\displaystyle c_{4}=1}$ ${\displaystyle c_{5}=1}$ ${\displaystyle (0,0,2,1,1)}$ $${\displaystyle 0\times 0!+0\times 1!+2\times 2!+1\times 3!+1\times 4!=34.}$$

De manera más general, los investigadores de algoritmos combinatorios han definido un código Gray para un conjunto de objetos combinatorios como un orden de los objetos en el que cada dos objetos consecutivos difieren en la forma mínima posible. En este sentido generalizado, el algoritmo Steinhaus-Johnson-Trotter genera un código Gray para las permutaciones mismas. ^[11]

Historia

El método fue conocido durante gran parte de su historia como un método para cambiar el repique de las campanas de la iglesia: proporciona un procedimiento mediante el cual se puede hacer sonar un conjunto de campanas a través de todas las permutaciones posibles, cambiando el orden de solo dos campanas por cambio. Estos llamados "cambios simples" o "caza simple" se conocían alrededor de 1621 por cuatro campanas, ^[12] y el método general se remonta a un manuscrito inédito de 1653 de Peter Mundy . ^[6] Un libro de 1677 de Fabian Stedman enumera las soluciones para hasta seis campanas. ^[13] Más recientemente, los timbres de cambio se han atenido a la regla de que ninguna campana puede permanecer en la misma posición durante tres permutaciones consecutivas; esta regla es violada por los cambios simples, por lo que se han ideado otras estrategias que intercambian múltiples campanas por cambio. ^[14]

El algoritmo lleva el nombre de Hugo Steinhaus , Selmer M. Johnson y Hale F. Trotter . Johnson y Trotter redescubrieron el algoritmo de forma independiente a principios de la década de 1960. ^[15] Un libro de Steinhaus de 1958, traducido al inglés en 1964, describe un rompecabezas imposible relacionado : generar todas las permutaciones mediante un sistema de partículas, cada una de las cuales se mueve a velocidad constante a lo largo de una línea e intercambia posiciones cuando una partícula supera a otra. ^[16] Un artículo de 1976 de Hu y Bien le dio crédito a Steinhaus por haber formulado el problema algorítmico de generar todas las permutaciones, ^[17] y en 1989 su libro había sido acreditado (incorrectamente) como una de las publicaciones originales del algoritmo. ^[18]

Ver también

• Algoritmo de Heap , un método diferente para enumerar todas las permutaciones
• Fisher-Yates shuffle , un método para generar permutaciones aleatorias

Notas

1. Sedgewick (1977).
2. Lenstra y Rinnooy Kan (1979); Salvaje (1997), sección 3; Pájaro (2010).
3. Williams (2013).
4. Johnson (1963).
5. Trotón (1962).
6. Knuth (2011).
7. Incluso (1973).
8. Ehrlich (1973); Dershowitz (1975); Sedgewick (1977); Pájaro (2010).
9. Véase, por ejemplo, la sección 11 de Savage (1997).
10. Dijkstra (1976); Knuth (2011).
11. Salvaje (1997).
12. Blanco (1996).
13. Stedman (1677); para obtener listas de cambios sencillos en hasta seis campanas, consulte las páginas 48 a 80.
14. McGuire (2003); Knuth (2011).
15. Johnson (1963); Trotón (1962).
16. Steinhaus (1964).
17. Hu y Tien (1976).
18. Ruskey (1989).

Referencias

• Bird, Richard (2010), "Capítulo 29: El algoritmo de Johnson-Trotter", Perlas del diseño de algoritmos funcionales , Cambridge University Press, págs. 251–257, doi :10.1017/cbo9780511763199, ISBN 9780511763199
• Dershowitz, Nachum (1975), "Un algoritmo simplificado sin bucles para generar permutaciones", Nordisk Tidskr. Manejo de información (BIT) , 15 (2): 158–164, doi :10.1007/bf01932689, MR  0502206, S2CID  121353303
• Dijkstra, Edsger W. (1976), "Sobre el guante lanzado por David Gries" (PDF) , Acta Informatica , 6 (4): 357–359, doi :10.1007/BF00268136, MR  0426492, S2CID  7085805. Aunque Dijkstra no cita ninguna literatura anterior, un borrador anterior EWD502 revela que conocía a Trotter (1962).
• Ehrlich, Gideon (1973), "Algoritmos sin bucle para generar permutaciones, combinaciones y otras configuraciones combinatorias", Journal of the ACM , 20 (3): 500–513, doi : 10.1145/321765.321781 , S2CID  21493963
• Incluso, Shimon (1973), Combinatoria algorítmica , Macmillan
• Hu, TC ; Tien, BN (octubre de 1976), "Generación de permutaciones con elementos no diferenciados", The American Mathematical Monthly , 83 (8): 629–631, doi :10.1080/00029890.1976.11994195, JSTOR  2319890
• Johnson, Selmer M. (1963), "Generación de permutaciones por transposición adyacente", Matemáticas de la Computación , 17 (83): 282–285, doi : 10.1090/S0025-5718-1963-0159764-2 , JSTOR  2003846, SEÑOR  0159764
• Lenstra, JK ; Rinnooy Kan, AHG (septiembre de 1979), "Un enfoque recursivo para la implementación de métodos enumerativos", Actas de la Escuela de Análisis y Diseño de Algoritmos en Optimización Combinatoria, Udine, Italia (PDF) , Informe técnico 8003/0, Universidad Erasmus Róterdam; consulte la Sección 2.1, "Un generador de cambio mínimo", págs. 3–8
• Knuth, Donald (2011), "Sección 7.2.1.2: Generación de todas las permutaciones", El arte de la programación informática, volumen 4A: Algoritmos combinatorios, Parte 1
• McGuire, Gary (2003), Campanas, moteles y grupos de permutación , CiteSeerX  10.1.1.6.5544
• Ruskey, Frank (1989), "Generación de transposición de permutaciones alternas", Orden , 6 (3): 227–233, doi :10.1007/BF00563523, MR  1048093
• Savage, Carla (1997), "Un estudio de códigos Gray combinatorios", SIAM Review , 39 (4): 605–629, Bibcode :1997SIAMR..39..605S, CiteSeerX  10.1.1.39.1924 , doi :10.1137/S0036144595295272 , JSTOR  2132693, SEÑOR  1491049
• Sedgewick, Robert (1977), "Métodos de generación de permutaciones", ACM Comput. Sobrevivir. , 9 (2): 137–164, doi : 10.1145/356689.356692 , S2CID  12139332
• Stedman, Fabian (1677), Campanalogia, o El arte de sonar mejorado, Londres: W. Godbid - a través de Early English Books Online Text Creation Partnership
• Steinhaus, Hugo (1964), Cien problemas de matemáticas elementales , Nueva York: Basic Books, págs. 49–50, MR  0157881
• Trotter, HF (agosto de 1962), "Algoritmo 115: Perm", Comunicaciones de la ACM , 5 (8): 434–435, doi : 10.1145/368637.368660 , S2CID  1013826
• White, Arthur T. (noviembre de 1996), "Fabian Stedman: ¿el primer teórico de grupos?", The American Mathematical Monthly , 103 (9): 771–778, doi :10.1080/00029890.1996.12004816, JSTOR  2974446
• Williams, Aaron (2013), "El algoritmo del código Grey codicioso", en Dehne, Frank; Solís-Oba, Roberto; Sack, Jörg-Rüdiger (eds.), Algoritmos y estructuras de datos - 13.º Simposio internacional, WADS 2013, Londres, ON, Canadá, 12 al 14 de agosto de 2013. Actas , Lecture Notes in Computer Science, vol. 8037, Springer, págs. 525–536, doi :10.1007/978-3-642-40104-6_46