Permutación ordenable por pila

En matemáticas y ciencias de la computación , una permutación ordenable por pila (también llamada permutación de árbol ) ^[1] es una permutación cuyos elementos pueden ordenarse mediante un algoritmo cuyo almacenamiento interno está limitado a una única estructura de datos de pila . Las permutaciones ordenables por pila son exactamente las permutaciones que no contienen el patrón de permutación 231; se cuentan mediante los números Catalan y se pueden colocar en biyección con muchos otros objetos combinatorios con la misma función de conteo, incluidos los caminos de Dyck y los árboles binarios .

Ordenar con una pila

El problema de ordenar una secuencia de entrada usando una pila fue planteado por primera vez por Knuth (1968), quien dio el siguiente algoritmo de tiempo lineal (estrechamente relacionado con los algoritmos para el problema posterior de todos los valores más pequeños más cercanos ):

• Inicializar una pila vacía
• Para cada valor de entrada x :
  • Mientras la pila no esté vacía y x sea más grande que el elemento superior de la pila, extraiga la pila a la salida
  • Empuja x sobre la pila
• Mientras la pila no esté vacía, sáquela a la salida.

Knuth observó que este algoritmo ordena correctamente algunas secuencias de entrada y no ordena otras. Por ejemplo, la secuencia 3,2,1 está correctamente ordenada: los tres elementos se colocan en la pila y luego se extraen en el orden 1,2,3. Sin embargo, la secuencia 2,3,1 no está correctamente ordenada: el algoritmo primero coloca 2 y lo extrae cuando ve el valor de entrada más grande, 3, lo que hace que 2 se muestre antes que 1 en lugar de después.

Debido a que este algoritmo es una ordenación por comparación , su éxito o fracaso no depende de los valores numéricos de la secuencia de entrada, sino solo de su orden relativo; es decir, una entrada puede describirse por la permutación necesaria para formar esa entrada a partir de una secuencia ordenada de la misma longitud. Knuth caracterizó las permutaciones que este algoritmo ordena correctamente como exactamente las permutaciones que no contienen el patrón de permutación 231: tres elementos x , y y z , que aparecen en la entrada en ese orden respectivo, con z  <  x  <  y . Además, observó que, si el algoritmo no ordena una entrada, entonces esa entrada no puede ordenarse con una sola pila.

Además de inspirar muchos trabajos posteriores sobre clasificación utilizando sistemas más complicados de pilas y estructuras de datos relacionadas, ^[2] la investigación de Knuth dio inicio al estudio de patrones de permutación y de clases de permutación definidas por patrones prohibidos.

Biyecciones y enumeración

La secuencia de empujes y estallidos que realiza el algoritmo de ordenamiento de Knuth al ordenar una permutación ordenable por pila forma un lenguaje Dyck : reinterpretar un empuje como un paréntesis izquierdo y un estallido como un paréntesis derecho produce una cadena de paréntesis balanceados. Además, cada cadena Dyck proviene de una permutación ordenable por pila de esta manera, y cada dos permutaciones diferentes ordenables por pila producen diferentes cadenas Dyck. Por esta razón, el número de permutaciones ordenables por pila de longitud n es el mismo que el número de cadenas Dyck de longitud 2 n , el número Catalan

${\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}.}$^[3]

Biyección entre árboles binarios (con nodos numerados de izquierda a derecha) y permutaciones ordenables por pila, generadas al enumerar los mismos números de nodo en preorden

Las permutaciones ordenables por pila también pueden traducirse directamente a y desde árboles binarios (sin etiquetar) , otra clase combinatoria cuya función de conteo es la secuencia de números Catalan. Un árbol binario puede transformarse en una permutación ordenable por pila numerando sus nodos en orden de izquierda a derecha y luego enumerando estos números en el orden en que serían visitados por un recorrido preordenado del árbol: primero la raíz, luego el subárbol izquierdo, luego el subárbol derecho, continuando recursivamente dentro de cada subárbol. En la dirección inversa, una permutación ordenable por pila puede decodificarse en un árbol en el que el primer valor x de la permutación corresponde a la raíz del árbol, los siguientes valores x  − 1 se decodifican recursivamente para dar el hijo izquierdo de la raíz, y los valores restantes se decodifican nuevamente recursivamente para dar el hijo derecho. ^[1]

Varias otras clases de permutaciones también pueden colocarse en biyección con las permutaciones ordenables en pila. Por ejemplo, las permutaciones que evitan los patrones 132, 213 y 312 pueden formarse respectivamente a partir de las permutaciones ordenables en pila (que evitan 231) invirtiendo la permutación, reemplazando cada valor x en la permutación por n  + 1 −  x , o ambas operaciones combinadas. Las permutaciones que evitan 312 también son las inversas de las permutaciones que evitan 231, y se han denominado permutaciones realizables en pila ya que son las permutaciones que pueden formarse a partir de la permutación de identidad mediante una secuencia de operaciones de inserción desde la entrada y extracción a la salida en una pila. ^[4] Como señaló Knuth (1968), las permutaciones que evitan 123 y 321 también tienen la misma función de conteo a pesar de estar menos relacionadas directamente con las permutaciones ordenables por pila.

Permutaciones aleatorias ordenables por pila

Rotem (1981) investiga las propiedades de las permutaciones ordenables por pila elegidas de manera uniforme al azar entre todas las permutaciones de una longitud dada. La longitud esperada de la subsecuencia descendente más larga en dicha permutación es , que difiere en un factor constante de las permutaciones aleatorias sin restricciones (para las que la longitud esperada es aproximadamente ). La longitud esperada de la secuencia ascendente más larga difiere aún más fuertemente de las permutaciones sin restricciones: es . El número esperado de valores dentro de la permutación que son mayores que todos los valores anteriores es solo , menor que su valor logarítmico para permutaciones sin restricciones. Y el número esperado de inversiones es , en contraste con su valor de para permutaciones sin restricciones. ${\displaystyle {\sqrt {\pi n}}-O(1)}$ ${\displaystyle 2{\sqrt {n}}}$ ${\displaystyle (n+1)/2}$ ${\displaystyle 3-6/(n+2)}$ ${\displaystyle \Theta (n^{3/2})}$ ${\displaystyle \Theta (n^{2})}$

Propiedades adicionales

Cada permutación define un grafo de permutación , un grafo cuyos vértices son los elementos de la permutación y cuyos bordes conectan pares de elementos que están invertidos por la permutación. Los grafos de permutación de permutaciones ordenables por pila son trivialmente perfectos . ^[4]

Para cada elemento i de una permutación p , defina b _i como el número de otros elementos que están a la izquierda de i y son mayores que i . Entonces p es ordenable por pila si y solo si, para todos los i , b _i  −  b _{i  + 1}  ≤ 1. ^[1]

Algoritmos

Knott (1977) utiliza la biyección entre permutaciones ordenables en pila y árboles binarios para definir un rango numérico para cada árbol binario y para construir algoritmos eficientes para calcular el rango de un árbol ("ranking") y para calcular el árbol con un rango dado ("unranking").

Micheli y Rossin (2006) definieron dos operaciones de edición en permutaciones: eliminación (crear un patrón de permutación ) y su inversa. Utilizando la misma correspondencia entre árboles y permutaciones, observaron que estas operaciones corresponden a la contracción de aristas en un árbol y su inversa. Aplicando un algoritmo de programación dinámica en tiempo polinomial para la distancia de edición en árboles, demostraron que la distancia de edición entre dos permutaciones ordenables por pila (y, por lo tanto, también el patrón común más largo) se puede encontrar en tiempo polinomial. Esta técnica se generalizó posteriormente a algoritmos para encontrar patrones comunes más largos de permutaciones separables ; ^[5] sin embargo, el problema del patrón común más largo es NP-completo para permutaciones arbitrarias. ^[6]

Notas

1. Knott (1977).
2. Tarjano (1972); Avis y recién nacido (1981); Rosenstiehl y Tarjan (1984); Bona (2002); Felsner y Pergel (2008). Véanse también las numerosas referencias adicionales proporcionadas por Bóna.
3. Knuth (1968); Rotem (1981).
4. Rotem (1981).
5. Bouvel, Rossin y Vialette (2007).
6. Micheli y Rossin (2006).

Referencias

• Avis, David ; Newborn, Monroe (1981), "Sobre las pilas de refrescos en serie", Utilitas Mathematica , 19 : 129–140, MR  0624050.
• Bóna, Miklós (2002), "Un estudio de las disciplinas de ordenamiento de pilas", Electronic Journal of Combinatorics , 9 (2): A1, doi : 10.37236/1693 , MR  2028290.
• Bouvel, Mathilde; Rossin, Dominique; Vialette, Stéphane (2007), "Longest common separable pattern among permutations", Combinatorial Pattern Matching (CPM 2007) , Notas de clase en informática, vol. 4580, Springer, págs. 316–327, doi :10.1007/978-3-540-73437-6_32, ISBN 978-3-540-73436-9.
• Felsner, Stefan; Pergel, Martin (2008), "La complejidad de la clasificación con redes de pilas y colas", Algorithms - ESA 2008 , Lecture Notes in Computer Science, vol. 5193, Karlsruhe, Alemania, págs. 417–429, doi :10.1007/978-3-540-87744-8_35, ISBN 978-3-540-87743-1{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).
• Knott, Gary D. (febrero de 1977), "Un sistema de numeración para árboles binarios", Communications of the ACM , 20 (2): 113–115, doi : 10.1145/359423.359434.
• Knuth, Donald (1968), "Vol. 1: Algoritmos fundamentales", El arte de la programación informática , Reading, Mass.: Addison-Wesley.
• Micheli, Anne; Rossin, Dominique (2006), "Distancia de edición entre árboles ordenados sin etiquetar", Informática teórica y aplicaciones , 40 (4): 593–609, arXiv : math/0506538 , doi :10.1051/ita:2006043, MR  2277052, S2CID  2259835.
• Rosenstiehl, Pierre ; Tarjan, Robert E. (1984), "Códigos de Gauss, gráficos hamiltonianos planares y permutaciones ordenables por pila", Journal of Algorithms , 5 (3): 375–390, doi :10.1016/0196-6774(84)90018-X, MR  0756164
• Rotem, D. (1981), "Permutaciones ordenables por pila", Discrete Mathematics , 33 (2): 185–196, doi :10.1016/0012-365X(81)90165-5, MR  0599081.
• Tarjan, Robert (abril de 1972), "Ordenación mediante redes de colas y pilas", Journal of the ACM , 19 (2): 341–346, doi : 10.1145/321694.321704.