correspondencia Robinson-Schensted es una correspondencia biyectiva entre permutaciones y pares de cuadros estándar de Young de la misma forma. Tiene varias descripciones, todas de naturaleza algorítmica, tiene muchas propiedades notables y tiene aplicaciones en combinatoria y otras áreas como la teoría de la representación . La correspondencia se ha generalizado de numerosas maneras, especialmente por Knuth a lo que se conoce como la correspondencia Robinson-Schensted-Knuth , y una generalización adicional a las imágenes de Zelevinsky.
La descripción más simple de la correspondencia está utilizando el algoritmo Schensted (Schensted 1961 ), un procedimiento que construye un cuadro al insertar sucesivamente los valores de la permutación de acuerdo con una regla específica, mientras que el otro cuadro registra la evolución de la forma durante la construcción. La correspondencia había sido descrita, en una forma bastante diferente, mucho antes por Robinson ( Robinson 1938 ), en un intento de probar la regla de Littlewood-Richardson . La correspondencia a menudo se conoce como el algoritmo Robinson-Schensted, aunque el procedimiento utilizado por Robinson es radicalmente diferente del algoritmo Schensted, y casi se olvida por completo. Otros métodos para definir la correspondencia incluyen un algoritmo no determinista en términos de jeu de taquin .
dónde denota el conjunto de particiones de n (o de diagramas Young con n cuadrados), y t λ denota el número de cuadros estándar Young de forma λ .
El algoritmo Schensted [ editar ]
El algoritmo Schensted comienza con la permutación σ escrita en notación de dos líneas.
donde σ i = σ ( i ) , y procede construyendo secuencialmente una secuencia de pares ordenados (intermedios) de cuadros jóvenes de la misma forma:
donde P 0 = Q 0 son cuadros vacíos. Los cuadros de salida son P = P n y Q = Q n . Una vez P i -1 se construye, uno forma P i por la inserción de σ i en P i -1 , y luego Q i añadiendo una entrada i a Q i -1 en la plaza añadió a la forma por la inserción (de modo que P i y Q itener formas iguales para todos i ). Debido a la función más pasiva de los cuadros Q i , el último Q n , que es parte de la salida y del que los Q i anteriores se leen fácilmente, se denomina cuadro de grabación ; por el contrario, los cuadros P i se denominan cuadros de inserción .
Inserción [ editar ]
El procedimiento básico utilizado para insertar cada σ i se llama inserción Schensted o inserción de fila (para distinguirlo de un procedimiento variante llamado inserción de columna). Su forma más simple se define en términos de "cuadros estándar incompletos": como los cuadros estándar tienen entradas distintas, formando filas y columnas crecientes, pero algunos valores (aún por insertar) pueden estar ausentes como entradas. El procedimiento toma como argumentos un cuadro T y un valor x no presente como entrada de T ; produce como resultado un nuevo cuadro denominado T ← xy un cuadrado s por el cual su forma ha crecido. El valor xaparece en la primera fila de T ← x , ya sea después de haber sido añadido al final (Si no hay entradas más grandes que x estaban presentes), o de otro modo la sustitución de la primera entrada y > x en la primera fila de T . En el primer caso, s es el cuadrado donde se agrega x , y se completa la inserción; en el último caso, la entrada reemplazada y se inserta de manera similar en la segunda fila de T , y así sucesivamente, hasta que en algún momento se aplique el primer caso (lo que ciertamente sucede si se alcanza una fila vacía de T ).
Más formalmente, el siguiente pseudocódigo describe la fila-inserción de un nuevo valor de x en T . [1]
- Conjunto i = 1 y j a uno más que la longitud de la primera fila de T .
- Mientras que j > 1 y x < T i , j −1 , disminuya j en 1. (Ahora ( i , j ) es el primer cuadrado en la fila i con una entrada mayor que x en T , o ninguna entrada).
- Si el cuadrado ( i , j ) está vacío en T , termine después de agregar x a T en el cuadrado ( i , j ) y estableciendo s = ( i , j ) .
- Intercambie los valores x y T i, j . (Esto inserta la x anterior en la fila i , y guarda el valor que reemplaza para su inserción en la siguiente fila).
- Aumente i en 1 y regrese al paso 2.
La forma de T crece exactamente un cuadrado, es decir, s .
Corrección [ editar ]
El hecho de que T ← x tenga filas y columnas crecientes, si lo mismo vale para T , no es obvio en este procedimiento (las entradas en la misma columna nunca se comparan). Sin embargo, se puede ver de la siguiente manera. En todo momento, excepto inmediatamente después del paso 4, el cuadrado ( i , j ) está vacío en T o tiene un valor mayor que x ; paso 5 re-establece esta propiedad porque ( i , j ) ahora es el cuadrado inmediatamente por debajo de la que contenía originalmente x en T . Por lo tanto, el efecto del reemplazo en el paso 4 sobre el valorT i, j es para hacerlo más pequeño; en particular no puede ser mayor que su derecho o vecinos inferiores. Por otro lado, el nuevo valor no es menor que su vecino izquierdo (si está presente), como lo garantiza la comparación que acaba de terminar el paso 2. Finalmente, para ver que el nuevo valor es mayor que su vecino superior T i −1, j si está presente, observe que T i −1, j se cumple después del paso 5, y que disminuir j en el paso 2 solo disminuye el valor correspondiente T i - 1, j .
Construyendo los cuadros [ editar ]
El algoritmo completo de Schensted aplicado a una permutación σ procede de la siguiente manera.
- Establezca P y Q en el cuadro vacío
- Para i creciente desde 1 a n compute P ← sigma i y el cuadrado s por el procedimiento de inserción; luego reemplace P por P ← σ i y agregue la entrada i al cuadro Q en el cuadrado s .
- Terminar, devolviendo el par ( P , Q ) .
El algoritmo produce un par de cuadros Young estándar.
Invertibilidad de la construcción [ editar ]
Se puede ver que dado cualquier par ( P , Q ) de cuadros de Young estándar de la misma forma, existe un procedimiento inverso que produce una permutación que dará lugar a ( P , Q ) por el algoritmo Schensted. Básicamente consiste en seguir los pasos del algoritmo hacia atrás, cada vez que se usa una entrada de Q para encontrar el cuadrado donde debe comenzar la inserción inversa, moviendo la entrada correspondiente de Pa la fila anterior, y continuando hacia arriba a través de las filas hasta que se reemplaza una entrada de la primera fila, que es el valor insertado en el paso correspondiente del algoritmo de construcción. Estos dos algoritmos inversos definen una correspondencia biyectiva entre permutaciones de n en un lado y pares de cuadros estándar de Young de igual forma y que contienen n cuadrados en el otro lado.
Propiedades [ editar ]
Una de las propiedades más fundamentales, pero no evidente a partir de la construcción algorítmica, es la simetría:
- Si la correspondencia Robinson-Schensted asocia cuadros ( P , Q ) a una permutación σ , entonces asocia ( Q , P ) a la permutación inversa σ −1 .
Propiedades adicionales, todas suponiendo que la correspondencia asocia cuadros ( P , Q ) a la permutación σ = ( σ 1 , ..., σ n ) .
- En el par de cuadros ( P ′, Q ′) asociados a la permutación inversa ( σ n , ..., σ 1 ) , el cuadro P ′ es la transposición del cuadro P , y Q ′ es un cuadro determinado por Q , independientemente de P (es decir, la transposición del cuadro obtenido de Q por la involución de Schützenberger ).
- La longitud de la subsecuencia creciente más larga de σ 1 , ..., σ n es igual a la longitud de la primera fila de P (y de Q ).
- La longitud de la subsecuencia decreciente más larga de σ 1 , ..., σ n es igual a la longitud de la primera columna de P (y de Q ), como se deduce de las dos propiedades anteriores.
- El conjunto de descenso { i : σ i > σ i +1 } de σ es igual al conjunto de descenso { i : i +1 es estrictamente en una fila debajo de la fila de i } de Q .
- Identifique subsecuencias de π con sus conjuntos de índices. Es un teorema de Greene que para cualquier k ≥ 1 , el tamaño del conjunto más grande que se puede escribir como la unión de a lo sumo k subsecuencias crecientes es λ 1 + ... + λ k . En particular, λ 1 es igual a la longitud más grande de una subsecuencia creciente de π .
- Si σ es una involución , entonces el número de puntos fijos de σ es igual al número de columnas de longitud impar en λ .
;_Steinhaus%E2%80%93Johnson%E2%80%93Trotter.svg)
El algoritmo Steinhaus – Johnson – Trotter o el algoritmo Johnson – Trotter , también llamados 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 destacado". Además de ser simple y computacionalmente eficiente, tiene la ventaja de que los cálculos posteriores sobre las permutaciones que genera pueden acelerarse porque estas permutaciones son muy similares entre sí.
Estructura recursiva [ editar ]
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 en n - 1 elementos es una permutación par (como es cierto para las permutaciones primera, tercera, etc. en la secuencia), entonces el número n se coloca en todas las posiciones posibles en orden descendente, desde n hasta 1; cuando la permutación en n - 1 ítems es impar, el número n se coloca en todas las posiciones posibles en orden ascendente. [2]
Por lo tanto, 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, uno puede colocar el número 3 en cada una de las tres posiciones diferentes para estas tres 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 recursión, 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 para 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 los elementos primero y final de la secuencia, también, difieren en solo dos elementos adyacentes (las posiciones de los números 1 y 2), como se puede mostrar por inducción.
Aunque 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 mayor número en la secuencia generada recursivamente, el algoritmo actual de Steinhaus-Johnson-Trotter evita la recursión, en cambio calcula la misma secuencia de permutaciones por 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 en la lista de permutaciones antes. 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, lo que hemos visto antes, así que llegamos a 312, etc. La dirección de la transposición (izquierda o derecha) siempre se determina de manera única en este algoritmo.
Algoritmo [ editar ]
Como lo describe Johnson (1963) , el algoritmo para generar la próxima permutación a partir de una permutación dada π realiza los siguientes pasos
- Para cada i de 1 a n , sea x i la posición donde se coloca el valor i en la permutación π. Si el orden de los números del 1 al i - 1 en 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, puede modificarse fácilmente para generar solo las permutaciones pares o solo las permutaciones impares: para generar la próxima permutación de la misma paridad de una permutación dada, simplemente aplique el mismo procedimiento dos veces . [4]
La aceleración de Even [ editar ]
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 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 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:
- 3 1 −2
Después de cada paso, todos los elementos mayores que el elemento elegido (que anteriormente tenía la dirección cero) tienen sus direcciones establecidas 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 el número 2 se mueve, 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 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 el número n toman solo 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 un pequeño número de permutaciones llevará una mayor cantidad de tiempo. [1]
Una versión sin bucle más compleja del mismo procedimiento permite que se realice 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 [ editar ]
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 se define de esta manera en el espacio n -dimensional, en realidad es un politopo ( n - 1) -dimensional; Por ejemplo, el permutoedro en cuatro elementos es un poliedro tridimensional, el octaedro truncado . Si cada vértice del permutoedro está marcado por la permutación inversa a la permutación definida por sus coordenadas de vértice, el etiquetado resultante describe un gráfico de Cayleydel grupo simétrico de permutaciones en n elementos, según lo generado por las permutaciones que intercambian pares de elementos adyacentes. Por lo tanto, 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 un borde en el permutoedro, y toda la secuencia de permutaciones describe un camino hamiltoniano en el permutoedro, un camino que pasa a través de cada vértice exactamente una vez. Si la secuencia de permutaciones se completa agregando un borde más desde la última permutación a la primera en la secuencia, el resultado es un ciclo hamiltoniano. [6]
Relación con los códigos grises [ editar ]
Un código gris para números en una raíz 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. El n ! Las permutaciones de los n números del 1 al n 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 inversionespara el cual i es el mayor de los dos valores invertidos), y luego interpretar estas secuencias como números en el sistema de números factoriales , es decir, el sistema de radix mixto con secuencia de radix (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 un número de inversiones que difieren en uno, formando un código Gray para el sistema de números factoriales. [7]
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 orden para los objetos en los que cada dos objetos consecutivos difieren de la manera mínima posible. En este sentido generalizado, el algoritmo Steinhaus – Johnson – Trotter genera un código Gray para las permutaciones mismas.
Historia [ editar ]
El algoritmo lleva el nombre de Hugo Steinhaus , Selmer M. Johnson y Hale F. Trotter. Johnson y Trotter descubrieron el algoritmo independientemente el uno del otro 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 rompecabezas relacionado de generar todas las permutaciones mediante un sistema de partículas, cada una moviéndose a una velocidad constante a lo largo de una línea e intercambiando posiciones cuando una partícula adelanta a otra. No hay solución posible 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 un método para cambiar el sonido de las campanas de la iglesia: proporciona un procedimiento mediante el cual se puede tocar 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 han cumplido con una 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.
No hay comentarios:
Publicar un comentario