El algoritmo Steinhaus-Johnson-Trotter o el algoritmo 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 n elementos. Cada permutación en la secuencia que genera difiere de la permutación anterior al intercambiar dos elementos adyacentes de la secuencia. De manera equivalente, este algoritmo encuentra un ciclo hamiltoniano en el permutoedro .
Este método ya era conocido por los timbres de cambio ingleses del siglo XVII , y Sedgewick (1977) lo llama "quizás el algoritmo de enumeración de permutación más prominente". Además de ser simple y eficiente desde el punto de vista computacional, tiene la ventaja de que los cálculos posteriores de las permutaciones que genera pueden acelerarse porque estas permutaciones son muy similares entre sí. [1]
Estructura recursiva
La secuencia de permutaciones para un número dado n se puede formar a partir de la secuencia de permutaciones para n - 1 colocando el número n en cada posición posible en cada una de las permutaciones más cortas. Cuando la permutación de n - 1 elementos es una permutación par (como ocurre con la primera, la tercera, etc., permutaciones de la secuencia), entonces el número n se coloca en todas las posiciones posibles en orden descendente, de n a 1; cuando la permutación de n - 1 elementos es impar, el número n se coloca en todas las posiciones posibles en orden ascendente. [2]
Así, a partir de la permutación única en un elemento,
- 1
uno 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 las 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
En el siguiente nivel de recursividad, el número 4 se colocaría en orden descendente en 1 2 3 , en orden ascendente en 1 3 2 , en orden descendente en 3 1 2 , etc. El mismo patrón de ubicación, alternando entre ubicaciones descendentes y ascendentes de n , se aplica a cualquier valor mayor de n . De esta manera, cada permutación difiere de la anterior ya sea por el movimiento de una sola posición a la vez de n , 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 solo la transposición de dos elementos adyacentes. Cuando n > 1, el primer y último elemento de la secuencia, también, difieren sólo en dos elementos adyacentes (las posiciones de los números 1 y 2), como puede mostrarse por inducción.
Aunque esta secuencia se puede generar 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 de forma recursiva, el algoritmo Steinhaus-Johnson-Trotter real evita la recursividad, en lugar de calcular la misma secuencia de permutaciones mediante un método iterativo.
Existe una definición equivalente y conceptualmente algo más simple del ordenamiento de permutaciones de Steinhaus-Johnson-Trotter a través del siguiente algoritmo codicioso: [3] Comenzamos con la permutación de identidad. Ahora transponemos repetidamente la entrada más grande posible con la entrada a su izquierda o derecha, de modo que en cada paso, se crea una nueva permutación que no se ha encontrado antes en la lista de permutaciones. Por ejemplo, en el caso comenzamos con 123, luego volteamos 3 con su vecino izquierdo y obtenemos 132. Luego volteamos 3 con su vecino izquierdo 1, ya que voltear 3 con su vecino derecho 2 produciría nuevamente 123, que hemos visto antes, así que llegamos a 312, etc. La dirección de la transposición (izquierda o derecha) siempre se determina de forma única en este algoritmo.
Algoritmo
Como lo describe Johnson (1963) , el algoritmo para generar la siguiente permutación a partir de una permutación dada π realiza los siguientes pasos
- Para cada i de 1 an , sea x i la posición donde el valor i se coloca en la permutación π. Si el orden de los números de 1 a i - 1 en la permutación π define una permutación par , sea y i = x i - 1; de lo contrario, sea y i = x i + 1.
- Encuentre el número más grande i para el cual y i define una posición válida en la permutación π que contiene un número menor que i . Intercambie los valores en las posiciones x i e y i .
Cuando no se puede encontrar ningún número i que cumpla las condiciones del segundo paso del algoritmo, el algoritmo ha alcanzado la permutación final de la secuencia y termina. Este procedimiento puede implementarse en O ( n ) tiempo por permutación.
Trotter (1962) ofrece una implementación alternativa de un algoritmo iterativo para la misma secuencia, en notación ALGOL 60 ligeramente comentada .
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 permutaciones 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. . [4]
Incluso se acelera
Una mejora posterior de 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 de Johnson del algoritmo). 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 el 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. Por lo tanto, en este ejemplo, después de que se mueva el número 2, el número 3 se vuelve a marcar con una dirección:
- +3 2 1
Los dos pasos restantes del algoritmo para n = 3 son:
- 2 +3 1
- 2 1 3
Cuando todos los números quedan sin marcar, el algoritmo termina.
Este algoritmo toma el tiempo O ( i ) para cada paso en el que el mayor número para moverse es n - i + 1. Por lo tanto, los intercambios que involucran al número n toman solo un tiempo constante; Dado que estos intercambios representan todos menos una fracción de 1 / 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]
Una versión sin bucles más compleja del mismo procedimiento 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. [5]
Interpretación geométrica
El conjunto de todas las permutaciones de n elementos puede representarse geométricamente por un permutoedro , el politopo formado a partir del casco convexo de n ! vectores, las permutaciones del vector (1,2, ... n ). Aunque definido de esta manera en el espacio n -dimensional, en realidad es un politopo ( n - 1) -dimensional; 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 n elementos, generado por las permutaciones que intercambian pares adyacentes de elementos. 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 extremos 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 un borde más de la última permutación al primero de la secuencia, el resultado es en cambio un ciclo hamiltoniano. [6]
Relación con los códigos Gray
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. ¡La n ! las permutaciones de los n números de 1 an se pueden colocar en correspondencia uno a uno con el n ! números del 0 al n ! - 1 emparejando cada permutación con la secuencia de números c i que cuentan el número de posiciones en la permutación que están a la derecha del valor i y que contienen un valor menor que i (es decir, el número de inversiones para las cuales i 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 base mixto con secuencia de base (1,2,3,4, ...). Por ejemplo, la permutación (3,1,4,5,2) daría los valores c 1 = 0, c 2 = 0, c 3 = 2, c 4 = 1 y c 5 = 1. La secuencia de estos valores, (0,0,2,1,1), da el número
- 0 × 0! + 0 × 1! + 2 × 2! + 1 × 3! + 1 × 4! = 34.
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 Gray para el sistema numérico factorial. [7]
De manera más general, los investigadores de algoritmos combinatorios han definido un código Gray para un conjunto de objetos combinatorios que es un ordenamiento de los objetos en el que cada dos objetos consecutivos difieren en la mínima forma posible. En este sentido generalizado, el algoritmo Steinhaus-Johnson-Trotter genera un código Gray para las permutaciones mismas.
Historia
El algoritmo lleva el nombre de Hugo Steinhaus , Selmer M. Johnson y Hale F. Trotter . Johnson y Trotter descubrieron el algoritmo de forma independiente a principios de la década de 1960. Un libro de Steinhaus, publicado originalmente en 1958 y traducido al inglés en 1963, describe un acertijo relacionado de generar todas las permutaciones mediante un sistema de partículas, cada una moviéndose a velocidad constante a lo largo de una línea e intercambiando posiciones cuando una partícula alcanza a otra. No es posible una solución para n > 3, porque el número de intercambios es mucho menor que el número de permutaciones, pero el algoritmo Steinhaus-Johnson-Trotter describe el movimiento de partículas con velocidades no constantes que generan todas las permutaciones.
Fuera de las matemáticas, el mismo método se conoció durante mucho más tiempo como 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" se registraron ya en 1621 para cuatro campanas, y un libro de 1677 de Fabian Stedman enumera las soluciones para hasta seis campanas. Más recientemente, los timbres de cambio se han regido por una regla según la cual 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. [8]
Ver también
- Algoritmo de montón
- Reproducción aleatoria de Fisher-Yates
Notas
- ↑ a b Sedgewick (1977) .
- ^ Savage (1997) , sección 3.
- ^ Williams, Aaron (2013). "El codicioso algoritmo del código Gray". Actas del XIII Simposio Internacional sobre Algoritmos y Estructuras de Datos (WADS) . Londres (Ontario, Canadá). págs. 525–536. doi : 10.1007 / 978-3-642-40104-6_46 .
- ^ Knuth (2011) .
- ^ Ehrlich (1973) ; Dershowitz (1975) ; Sedgewick (1977) .
- ^ Véase, por ejemplo, la sección 11 de Savage (1997) .
- ^ Dijkstra (1976) ; Knuth (2011) .
- ^ McGuire (2003) ; Knuth (2011) .
Referencias
- Dershowitz, Nachum (1975), "Un algoritmo simplificado sin bucles para generar permutaciones", Nordisk Tidskr. Manipulación de información (BIT) , 15 (2): 158–164, doi : 10.1007 / bf01932689 , MR 0502206.
- Dijkstra, Edsger W. (1976), "En un guante lanzado por David Gries" (PDF) , Acta Informatica , 6 (4): 357–359, doi : 10.1007 / BF00268136 , MR 0426492. Aunque DIjkstra no cita ninguna literatura anterior, un borrador anterior de 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.
- Incluso, Shimon (1973), combinatoria algorítmica , Macmillan.
- Johnson, Selmer M. (1963), "Generación de permutaciones por transposición adyacente", Matemáticas de Computación , 17 : 282-285, doi : 10.1090 / S0025-5718-1963-0159764-2 , JSTOR 2003846 , MR 0159764.
- 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.
- McGuire, Gary (2003), Bells, moteles y grupos de permutación , CiteSeerX 10.1.1.6.5544.
- Savage, Carla (1997), "A survey of combinatorial Gray codes", SIAM Review , 39 (4): 605–629, CiteSeerX 10.1.1.39.1924 , doi : 10.1137 / S0036144595295272 , JSTOR 2132693 , MR 1491049.
- Sedgewick, Robert (1977), "Métodos de generación de permutación", ACM Comput. Surv. , 9 (2): 137–164, doi : 10.1145 / 356689.356692.
- Steinhaus, Hugo (1964), Cien problemas en matemáticas elementales , Nueva York: Basic Books, págs. 49–50, MR 0157881.
- Trotter, HF (agosto de 1962), "Algoritmo 115: Perm", Comunicaciones del ACM , 5 (8): 434–435, doi : 10.1145 / 368637.368660.