En matemáticas y ciencias de la computación , una permutación ordenable en pila (también llamada permutación de árbol ) [1] es una permutación cuyos elementos pueden ser ordenados por un algoritmo cuyo almacenamiento interno está limitado a una estructura de datos de pila única . Las permutaciones ordenables en pila son exactamente las permutaciones que no contienen el patrón de permutación 231; se cuentan por los números catalanes y se pueden colocar en biyección con muchos otros objetos combinatorios con la misma función de conteo, incluidos los caminos Dyck y los árboles binarios.
Clasificando 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 último problema de valores más pequeños más cercanos ):
- Inicializar una pila vacía
- Para cada valor de entrada x :
- Si bien la pila no está vacía y x es más grande que el elemento superior de la pila, coloque la pila en la salida
- Empuje x en la pila
- Mientras la pila no esté vacía, colóquela en 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á ordenada correctamente: los tres elementos se colocan en la pila y luego se abren en el orden 1, 2, 3. Sin embargo, la secuencia 2, 3, 1 no está ordenada correctamente: el algoritmo primero presiona 2 y lo muestra cuando ve el valor de entrada más grande 3, lo que hace que 2 salga antes de 1 en lugar de después de él.
Debido a que este algoritmo es un tipo de 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 mediante 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 clasifica correctamente como exactamente las permutaciones que no contienen el patrón de permutación 231: tres elementos x , y , yz , que aparecen en la entrada en ese orden respectivo, con z < x < y . Además, observó que, si el algoritmo no clasifica una entrada, esa entrada no se puede clasificar con una sola pila.
Además de inspirar mucho trabajo posterior sobre clasificación utilizando sistemas más complicados de pilas y estructuras de datos relacionadas, [2] la investigación de Knuth inició el estudio de patrones de permutación y de clases de permutación definidas por patrones prohibidos.
Biyecciones y enumeración
La secuencia de empujones y estallidos realizada por el algoritmo de clasificación de Knuth al ordenar una permutación ordenable en pila de un lenguaje Dyck : reinterpretar un empujón como un paréntesis izquierdo y un pop como un paréntesis derecho produce una cadena de paréntesis equilibrados. Además, cada cadena Dyck proviene de una permutación ordenable en pila de esta manera, y cada dos permutaciones diferentes ordenables en pila producen cadenas 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 Dyck de longitud 2 n , el número catalán
Las permutaciones ordenables en pila también se pueden traducir directamente hacia y desde árboles binarios (sin etiquetar) , otra clase combinatoria cuya función de conteo es la secuencia de números catalanes. Un árbol binario puede transformarse en una permutación ordenable en 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 de 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 se puede decodificar 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 de forma recursiva para dar el hijo izquierdo de la raíz. , y los valores restantes se decodifican nuevamente de forma recursiva para dar el hijo correcto. [1]
Varias otras clases de permutaciones también se pueden colocar 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 (evitando 231) invirtiendo la permutación, reemplazando cada valor x en la permutación por n + 1 - x , o ambas operaciones combinadas. Las permutaciones de evitación 312 son también las inversas de las permutaciones de evitación 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 empujar desde entrada y pop- operaciones de salida en una pila. [4] Como señaló Knuth (1968) , las permutaciones que evitan 123 y evitan 321 también tienen la misma función de conteo a pesar de estar menos directamente relacionadas con las permutaciones ordenables en pila.
Permutaciones aleatorias apilables
Rotem (1981) investiga las propiedades de las permutaciones ordenables en pila elegidas uniformemente al azar entre todas esas permutaciones de una longitud determinada. La longitud esperada de la subsecuencia descendente más larga en tal permutación es, que difieren en un factor constante de las permutaciones aleatorias no restringidas (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 no restringidas: 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 no restringidas. Y el número esperado de inversiones es, en contraste con su valor de para permutaciones ilimitadas.
Propiedades adicionales
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 gráficos de permutación de permutaciones ordenables en 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 apilable si y solo si, para todo 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 ("clasificación") y para calcular el árbol con un determinado rango ("unranking").
Micheli y Rossin (2006) definieron dos operaciones de edición sobre permutaciones: eliminación (hacer un patrón de permutación ) y su inversa. Usando la misma correspondencia entre árboles y permutaciones, observaron que estas operaciones corresponden a la contracción del borde 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 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 de patrón común más largo es NP-completo para permutaciones arbitrarias. [6]
Notas
- ↑ a b c Knott (1977) .
- ^ Tarjan (1972) ; Avis y recién nacido (1981) ; Rosenstiehl y Tarjan (1984) ; Bóna (2002) ; Felsner y Pergel (2008) . Véanse también las numerosas referencias adicionales dadas por Bóna.
- ^ Knuth (1968) ; Rotem (1981) .
- ↑ a b Rotem (1981) .
- ^ Bouvel, Rossin y Vialette (2007) .
- ^ Micheli y Rossin (2006) .
Referencias
- Avis, David ; Newborn, Monroe (1981), "On pop-stacks in series", Utilitas Mathematica , 19 : 129-140, MR 0624050.
- Bóna, Miklós (2002), "Una encuesta de disciplinas de clasificación de pilas" , Revista Electrónica de Combinatoria , 9 (2): A1, MR 2028290.
- Bouvel, Mathilde; Rossin, Dominique; Vialette, Stéphane (2007), "Patrón separable común más largo entre permutaciones", Coincidencia de patrones combinatorios (CPM 2007) , Lecture Notes in Computer Science, 4580 , Springer, págs. 316–327, doi : 10.1007 / 978-3-540- 73437-6_32.
- Felsner, Stefan; Pergel, Martin (2008), "La complejidad de ordenar con redes de pilas y colas", Proc. 16º Eur. Symp. Algoritmos , Karlsruhe, Alemania, págs. 417–429, doi : 10.1007 / 978-3-540-87744-8_35 , ISBN 978-3-540-87743-1.
- 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 , Lectura, Mass .: Addison-Wesley.
- Micheli, Anne; Rossin, Dominique (2006), "Editar la distancia entre árboles ordenados sin etiquetar", Informática y aplicaciones teóricas , 40 (4): 593–609, arXiv : math / 0506538 , doi : 10.1051 / ita: 2006043 , MR 2277052.
- Rosenstiehl, Pierre ; Tarjan, Robert E. (1984), "Códigos de Gauss, gráficos planos hamiltonianos y permutaciones ordenables en pila", Journal of Algorithms , 5 (3): 375–390, doi : 10.1016 / 0196-6774 (84) 90018-X , MR 0756164
- Rotem, D. (1981), "Permutaciones ordenables en 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.