Permutación ordenable mediante pila

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

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 algoritmos para el problema posterior de todos los valores más pequeños más cercanos ):

• Inicializa una pila vacía
• Para cada valor de entrada x :
  • Mientras la pila no esté vacía y x sea mayor que el elemento superior de la pila, extraiga un elemento de la pila y colóquelo en la salida.
  • Empuja x a la pila
• Mientras la pila no esté vacía, muévala a la salida.

Knuth observó que este algoritmo ordena correctamente algunas secuencias de entrada, pero falla en otras. Por ejemplo, la secuencia 3,2,1 se ordena correctamente: los tres elementos se insertan en la pila y luego se extraen en el orden 1,2,3. Sin embargo, la secuencia 2,3,1 no se ordena correctamente: el algoritmo primero inserta el 2 y lo extrae cuando encuentra el valor de entrada mayor, el 3, lo que provoca que el 2 se muestre antes que el 1 en lugar de después.

Dado que este algoritmo es de ordenación por comparación , su éxito o fracaso no depende de los valores numéricos de la secuencia de entrada, sino únicamente de su orden relativo; es decir, una entrada puede describirse mediante la permutación necesaria para formarla a partir de una secuencia ordenada de la misma longitud. Knuth caracterizó las permutaciones que este algoritmo ordena correctamente como aquellas 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 logra ordenar una entrada, entonces esa entrada no puede ordenarse con una sola pila.

Además de inspirar muchos trabajos posteriores sobre ordenació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.

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

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

Las permutaciones ordenables en 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 de Catalan. Un árbol binario puede transformarse en una permutación ordenable en pila numerando sus nodos de izquierda a derecha y luego enumerando estos números en el orden en que serían visitados por un recorrido en preorden 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 en 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 x  − 1 valores 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 ]}

También se pueden colocar otras clases de permutaciones en biyección con las permutaciones ordenables en pila. Por ejemplo, las permutaciones que evitan los patrones 132, 213 y 312 se pueden formar, respectivamente, a partir de las permutaciones ordenables en pila (que evitan el patrón 231) invirtiendo la permutación, reemplazando cada valor x en la permutación por n  + 1 −  x , o combinando ambas operaciones. Las permutaciones que evitan el patrón 312 son también las inversas de las permutaciones que evitan el patrón 231, y se han denominado permutaciones realizables en pila, ya que son las permutaciones que se pueden formar a partir de la permutación identidad mediante una secuencia de operaciones de inserción y extracción 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 directamente relacionadas con las permutaciones ordenables por pila.

Rotem (1981) investiga las propiedades de permutaciones ordenables por pila elegidas uniformemente 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 por un factor constante de las permutaciones aleatorias sin restricciones (para las cuales 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})}$

Cada permutación define un grafo de permutación , un grafo cuyos vértices son los elementos de la permutación y cuyas aristas conectan pares de elementos que son 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 , definimos b _i como el número de otros elementos que están a la izquierda de i y son mayores que él . Entonces p es ordenable en pila si y solo si, para todo i , b _i  −  b _{i  + 1}  ≤ 1. ^{[ 1 ]}

Knott (1977) utiliza la biyección entre permutaciones ordenables por 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: la eliminación (que crea 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. Al aplicar un algoritmo de programación dinámica de tiempo polinomial para la distancia de edición en árboles, demostraron que la distancia de edición entre dos permutaciones ordenables en pilas (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 ]}

• Avis, David ; Newborn, Monroe (1981), "Sobre pilas de pop en series", Utilitas Mathematica , 19 : 129–140 , MR  0624050.
• Bóna, Miklós (2002), "Un estudio de las disciplinas de ordenación de pilas" , Electronic Journal of Combinatorics , 9 (2) A1, doi : 10.37236/1693 , MR  2028290.
• Bouvel, Mathilde; Rossin, Dominique; Vialette, Stéphane (2007), "Patrón separable común más largo entre permutaciones", Combinatorial Pattern Matching (CPM 2007) , Lecture Notes in Computer Science, vol. 4580, Springer, pp.  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 ordenación con redes de pilas y colas", Algorithms - ESA 2008 , Lecture Notes in Computer Science, vol. 5193, Karlsruhe, Alemania, pp.  417–429 , doi : 10.1007/978-3-540-87744-8_35 , ISBN 978-3-540-87743-1{{citation}}: CS1 mantenimiento: falta el editor de ubicación ( 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", Theoretical Informatics and Applications , 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, grafos 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", Matemáticas Discretas , 33 (2): 185– 196, doi : 10.1016/0012-365X(81)90165-5 , MR  0599081.
• Tarjan, Robert (abril de 1972), "Clasificación mediante redes de colas y pilas", Journal of the ACM , 19 (2): 341– 346, doi : 10.1145/321694.321704.