Algoritmo de Steinhaus-Johnson-Trotter

La secuencia de permutaciones para un número dado${\displaystyle n}$se puede formar a partir de la secuencia de permutaciones para${\displaystyle n-1}$colocando el número${\displaystyle n}$en cada posición posible en cada una de las permutaciones más cortas. El algoritmo de Steinhaus-Johnson-Trotter sigue esta estructura: la secuencia de permutaciones que genera consiste en${\displaystyle (n-1)!}$bloques de permutaciones, de modo que dentro de cada bloque las permutaciones coincidan en el orden de los números del 1 al${\displaystyle n-1}$y difieren únicamente en la posición de${\displaystyle n}$. Los bloques mismos se ordenan recursivamente, según el algoritmo de Steinhaus-Johnson-Trotter para un elemento menos. Dentro de cada bloque, las posiciones en las que${\displaystyle n}$se colocan en orden descendente o ascendente, y los bloques alternan entre estos dos órdenes: las colocaciones de${\displaystyle n}$En el primer bloque están 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 ]}

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

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,

Entonces, 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:

El mismo patrón de colocación, alternando entre colocaciones descendentes y ascendentes de${\displaystyle n}$, se aplica a cualquier valor mayor de${\displaystyle n}$. ^{[ 2 ]} En secuencias de permutaciones con esta estructura recursiva, cada permutación difiere de la anterior ya sea por el movimiento de una posición a la vez de${\displaystyle n}$o mediante 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 simplemente la transposición de dos elementos adyacentes. Cuando${\displaystyle n>1}$El primer y el último elemento de la secuencia también difieren en solo dos elementos adyacentes (las posiciones de los números).${\displaystyle 1}$y${\displaystyle 2}$), como puede probarse por inducción.

Esta secuencia puede ser generada por 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 ordenamiento de permutaciones también puede describirse de manera equivalente como el ordenamiento generado por el siguiente algoritmo voraz . ^{[ 3 ]} Comience con la permutación identidad${\displaystyle 1\;2\;\ldots \;n}$Ahora, transponga repetidamente la entrada más grande posible con la entrada a su izquierda o derecha, de manera 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${\displaystyle n=3}$La secuencia comienza con${\displaystyle 1\;2\;3}$, luego se voltea${\displaystyle 3}$con su vecino izquierdo para obtener${\displaystyle 1\;3\;2}$. Desde este punto, volteando${\displaystyle 3}$con su vecino derecho${\displaystyle 2}$produciría la permutación inicial${\displaystyle 1\;2\;3}$, por lo que la secuencia se invierte${\displaystyle 3}$con su vecino de la izquierda${\displaystyle 1}$y llega a${\displaystyle 3\;1\;2}$etc. La dirección de la transposición (izquierda o derecha) siempre se determina de forma única en este algoritmo. Sin embargo, el algoritmo real de Steinhaus-Johnson-Trotter no utiliza recursión y no necesita llevar un registro de las permutaciones que ya ha encontrado. En cambio, calcula la misma secuencia de permutaciones mediante un método iterativo simple .

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

• Para cada${\displaystyle i}$del 1 al${\displaystyle n}$, dejar${\displaystyle x_{i}}$ser la posición donde el valor${\displaystyle i}$se coloca en permutación${\displaystyle \pi }$. Si el orden de los números del 1 al${\displaystyle i-1}$en permutación${\displaystyle \pi }$define una permutación par , sea${\displaystyle y_{i}=x_{i}-1}$de lo contrario, deja${\displaystyle y_{i}=x_{i}+1}$.
• Encuentra el número más grande${\displaystyle i}$para qué${\displaystyle y_{i}}$define una posición válida en la permutación${\displaystyle \pi }$que contiene un número menor que${\displaystyle i}$. Intercambia los valores en las posiciones${\displaystyle x_{i}}$y${\displaystyle y_{i}}$.

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

Trotter ofrece una implementación alternativa de un algoritmo iterativo para la misma secuencia, en notación ALGOL 60 con comentarios breves . ^{[ 5 ]}

Debido a que este método genera permutaciones que alternan entre ser pares e impares, puede modificarse 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, basta con aplicar el mismo procedimiento dos veces. ^{[ 6 ]}

Una mejora posterior de Shimon Even optimiza el tiempo de ejecución del algoritmo al almacenar información adicional para cada elemento de la permutación: su posición y la dirección (positiva, negativa o cero) en la que se mueve actualmente (básicamente, esta es la misma información calculada utilizando 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:

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:

Si esto provoca que el elemento elegido alcance la primera o la ú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:

Después de cada paso, a todos los elementos mayores que el elemento elegido (que previamente tenía dirección cero) se les cambia la dirección para indicar movimiento hacia el elemento elegido. Es decir, positiva para todos los elementos entre el inicio de la permutación y el elemento elegido, y negativa 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 tener una dirección asignada:

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

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

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

Una versión más compleja y sin bucles del mismo procedimiento, adecuada para la programación funcional, permite que se ejecute 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 ]}

El conjunto de todas las permutaciones de${\displaystyle n}$Los elementos pueden representarse geométricamente mediante un permutoedro , el politopo formado a partir de la envoltura convexa de${\displaystyle n!}$vectores, las permutaciones del vector${\displaystyle (1,2,\dots n)}$. Aunque se define de esta manera en${\displaystyle n}$espacio -dimensional, en realidad es un${\displaystyle (n-1)}$politopo de dimensión ; por ejemplo, el permutoedro de cuatro elementos es un poliedro tridimensional, el octaedro truncado . Si cada vértice del permutoedro se etiqueta mediante la permutación inversa a la permutación definida por sus coordenadas de vértice, el etiquetado resultante describe un grafo de Cayley del grupo simétrico de permutaciones en${\displaystyle n}$elementos, generados por las permutaciones que intercambian pares adyacentes de elementos. Así, cada dos permutaciones consecutivas en la secuencia generada por el algoritmo de 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 añadiendo una arista más de la última permutación a la primera de la secuencia, el resultado es un ciclo hamiltoniano. ^{[ 9 ]}

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.${\displaystyle n!}$permutaciones de la${\displaystyle n}$números del 1 al${\displaystyle n}$puede ser colocado en correspondencia individual con el${\displaystyle n!}$números del 0 al${\displaystyle n!-1}$emparejando cada permutación con la secuencia de números${\displaystyle c_{i}}$que cuentan el número de posiciones en la permutación que están a la derecha del valor${\displaystyle i}$y que contienen un valor menor que${\displaystyle i}$(es decir, el número de inversiones para las cuales${\displaystyle i}$es el mayor de los dos valores invertidos), y luego interpretando estas secuencias como números en el sistema numérico factorial , es decir, el sistema de base mixta con secuencia de base${\displaystyle (1,2,3,4,\dots )}$Por ejemplo, la permutación${\displaystyle (3,1,4,5,2)}$daría los valores${\displaystyle c_{1}=0}$,${\displaystyle c_{2}=0}$,${\displaystyle c_{3}=2}$,${\displaystyle c_{4}=1}$, y${\displaystyle c_{5}=1}$. La secuencia de estos valores,${\displaystyle (0,0,2,1,1)}$, da el número $${\displaystyle 0\times 0!+0\times 1!+2\times 2!+1\times 3!+1\times 4!=34.}$$ Las permutaciones consecutivas en la secuencia generada por el algoritmo de Steinhaus-Johnson-Trotter tienen números de inversiones que difieren en uno, formando un código Gray para el sistema numérico factorial. ^{[ 10 ]}

En términos más generales, los investigadores de algoritmos combinatorios han definido un código Gray para un conjunto de objetos combinatorios como un ordenamiento de los objetos en el que cada par de objetos consecutivos difiere de la forma mínima posible. En este sentido generalizado, el algoritmo de Steinhaus-Johnson-Trotter genera un código Gray para las permutaciones mismas. ^{[ 11 ]}