Subsecuencia creciente más larga

Problema de informática

En informática , el problema de la subsecuencia creciente más larga tiene como objetivo encontrar una subsecuencia de una secuencia dada en la que los elementos de la subsecuencia estén ordenados en orden ascendente y en la que la subsecuencia sea lo más larga posible. Esta subsecuencia no es necesariamente contigua o única. Las subsecuencias crecientes más largas se estudian en el contexto de varias disciplinas relacionadas con las matemáticas , incluidas la algorítmica , la teoría de matrices aleatorias , la teoría de la representación y la física . ^{[1] [2]} El problema de la subsecuencia creciente más larga se puede resolver en el tiempo donde denota la longitud de la secuencia de entrada. ^[3] ${\displaystyle O(n\log n),}$ ${\displaystyle n}$

Ejemplo

En los primeros 16 términos de la secuencia binaria de Van der Corput

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

Una de las subsecuencias crecientes más largas es

0, 2, 6, 9, 11, 15.

Esta subsecuencia tiene una longitud de seis; la secuencia de entrada no tiene subsecuencias crecientes de siete miembros. La subsecuencia creciente más larga en este ejemplo no es la única solución: por ejemplo,

0, 4, 6, 9, 11, 15

0, 2, 6, 9, 13, 15

0, 4, 6, 9, 13, 15

son otras subsecuencias crecientes de igual longitud en la misma secuencia de entrada.

Relaciones con otros problemas algorítmicos

El problema de la subsecuencia creciente más larga está estrechamente relacionado con el problema de la subsecuencia común más larga , que tiene una solución de programación dinámica de tiempo cuadrático: la subsecuencia creciente más larga de una secuencia es la subsecuencia común más larga de y donde es el resultado de la clasificación. Sin embargo, para el caso especial en el que la entrada es una permutación de los números enteros , este enfoque se puede hacer mucho más eficiente, lo que lleva a límites de tiempo de la forma ^[4] ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle T,}$ ${\displaystyle T}$ ${\displaystyle S.}$ ${\displaystyle 1,2,\ldots ,n,}$ ${\displaystyle O(n\log \log n).}$

El grupo más grande en un gráfico de permutación corresponde a la subsecuencia decreciente más larga de la permutación que define el gráfico (asumiendo que la secuencia original no permutada está ordenada del valor más bajo al más alto). De manera similar, el conjunto independiente máximo en un gráfico de permutación corresponde a la subsecuencia no decreciente más larga. Por lo tanto, los algoritmos de subsecuencia creciente más larga se pueden utilizar para resolver el problema del grupo de manera eficiente en gráficos de permutación. ^[5]

En la correspondencia de Robinson-Schensted entre permutaciones y tablas de Young , la longitud de la primera fila de la tabla correspondiente a una permutación es igual a la longitud de la subsecuencia creciente más larga de la permutación, y la longitud de la primera columna es igual a la longitud de la subsecuencia decreciente más larga. ^[3]

Algoritmos eficientes

El algoritmo que se describe a continuación resuelve el problema de la subsecuencia creciente más larga de manera eficiente con arreglos y búsqueda binaria . Procesa los elementos de la secuencia en orden, manteniendo la subsecuencia creciente más larga encontrada hasta el momento. Denote los valores de la secuencia como etc. Luego, después del procesamiento, el algoritmo habrá almacenado un entero y valores en dos arreglos: ${\displaystyle X[0],X[1],\ldots ,}$ ${\displaystyle X[i],}$ ${\displaystyle L}$

• ${\displaystyle L}$— almacena la longitud de la subsecuencia creciente más larga encontrada hasta el momento.
• ${\displaystyle M[l]}$— almacena el índice del valor más pequeño tal que existe una subsecuencia creciente de longitud que termina en en el rango Explícitamente, suponga que denota el conjunto de todos los índices tales que y existe una subsecuencia creciente de longitud que termina en Entonces es el índice en para el cual se minimiza; lo que significa que y (o equivalentemente, y para cada ); si varios índices satisfacen esta condición, entonces es el más grande. ${\displaystyle k}$ ${\displaystyle X[k]}$ ${\displaystyle l}$ ${\displaystyle X[k]}$ ${\displaystyle k\leq i.}$ ${\displaystyle K_{i,l}}$ ${\displaystyle j}$ ${\displaystyle j\leq i}$ ${\displaystyle l}$ ${\displaystyle X[j].}$ ${\displaystyle k=M[l]}$ ${\displaystyle K_{i,l}}$ ${\displaystyle X[M[l]]}$ ${\displaystyle M[l]\in K_{i,l}}$ ${\displaystyle X[M[l]]=\min _{j\in K_{i,l}}X[j]}$ ${\displaystyle M[l]\in K_{i,l}}$ ${\displaystyle j\in K_{i,l},}$ ${\displaystyle X[M[l]]\leq X[j]}$ ${\displaystyle M[l]}$
  • Para aclarar, "existe una subsecuencia creciente de longitud que termina en " significa que existen índices que terminan en tales que ${\displaystyle l}$ ${\displaystyle X[k]}$ ${\displaystyle l}$ ${\displaystyle i_{1}<i_{2}<\cdots <i_{l}=k}$ ${\displaystyle k}$ ${\displaystyle X\left[i_{1}\right]<X\left[i_{2}\right]<\cdots <X[k].}$
  • Tenga en cuenta que porque representa la longitud de la subsecuencia creciente y representa el índice de su terminación. ${\displaystyle 1\leq l\leq i+1,}$ ${\displaystyle l\geq 1}$ ${\displaystyle k\geq 0}$
  • La longitud de es mayor que la longitud de pero es posible que el algoritmo no utilice todos los elementos de esta matriz (de hecho, si la secuencia creciente más larga tiene longitud, entonces solo se utilizan por el algoritmo). Sin embargo, si se utiliza/define entonces (y además, en la iteración también se cumplirá). no está definido ya que las secuencias de longitud no tienen índice final ( puede ser cualquier valor). ${\displaystyle M}$ ${\displaystyle 1}$ ${\displaystyle X}$ ${\displaystyle L}$ ${\displaystyle M[1],\ldots ,M[L]}$ ${\displaystyle M[l]}$ ${\displaystyle l-1\leq M[l]}$ ${\displaystyle i,}$ ${\displaystyle M[l]\leq i}$ ${\displaystyle M[0]}$ ${\displaystyle 0}$ ${\displaystyle M[0]}$
• ${\displaystyle P[k]}$— almacena el índice del predecesor de en la subsecuencia creciente más larga que termina en ${\displaystyle X[k]}$ ${\displaystyle X[k].}$
  • La longitud de es igual a la de ${\displaystyle P}$ ${\displaystyle X,}$
  • Si entonces while no está definido ya que no tiene predecesor ( puede ser cualquier valor). ${\displaystyle k>0}$ ${\displaystyle P[k]<k}$ ${\displaystyle P[0]}$ ${\displaystyle X[0]}$ ${\displaystyle P[0]}$

Debido a que el algoritmo a continuación utiliza numeración basada en cero , para mayor claridad se rellena con lo que no se utiliza de modo que corresponde a una subsecuencia de longitud. Una implementación real puede omitir y ajustar los índices en consecuencia. ${\displaystyle M}$ ${\displaystyle M[0],}$ ${\displaystyle M[l]}$ ${\displaystyle l.}$ ${\displaystyle M[0]}$

Nótese que, en cualquier punto del algoritmo, la secuencia es creciente. Porque, si hay una subsecuencia creciente cuya longitud termina en entonces también hay una subsecuencia cuya longitud termina en un valor menor: es decir, la que termina en Por lo tanto, podemos hacer búsquedas binarias en esta secuencia en tiempo logarítmico. $${\displaystyle X[M[1]],X[M[2]],\ldots ,X[M[L]]}$$ ${\displaystyle l\geq 2}$ ${\displaystyle X[M[l]],}$ ${\displaystyle l-1}$ ${\displaystyle X[P[M[l]]].}$

El algoritmo entonces procede de la siguiente manera:

Una demostración del código.

P = matriz de longitud NM = matriz de longitud N + 1M[0] = -1 // indefinido, por lo que se puede establecer en cualquier valorL = 0para i en el rango 0 a N-1: //N-1 incluido // Búsqueda binaria del menor positivo l ≤ L // tal que X[M[l]] >= X[i] lo = 1 hola = L + 1 mientras lo < hi: medio = bajo + piso((alto-bajo)/2) // bajo <= medio < alto si X[M[mid]] >= X[i] Hola = mediados de lo contrario : // si X[M[mid]] < X[i] lo = medio + 1 // Después de buscar, lo == hi es 1 mayor que el // longitud del prefijo más largo de X[i] nuevoL = lo // El predecesor de X[i] es el último índice de // la subsecuencia de longitud nuevaL-1 P[i] = M[nuevoL-1] M[nuevaL] = i  Si nuevoL > L: // Si encontramos una subsecuencia más larga que cualquiera de las que hemos // encontrado todavía, actualizar L L = nuevoL// Reconstruir la subsecuencia creciente más larga// Consiste en los valores de X en los índices L:// ..., P[P[M[L]]], P[M[L]], M[L]S = matriz de longitud Lk = M[L]para j en el rango L-1 a 0: //0 incluido S[j] = X[k] k = P[k]volver S

Debido a que el algoritmo realiza una única búsqueda binaria por cada elemento de la secuencia, su tiempo total puede expresarse utilizando la notación Big O , como Fredman (1975) analiza una variante de este algoritmo, que atribuye a Donald Knuth ; en la variante que estudia, el algoritmo prueba si cada valor puede usarse para extender la secuencia creciente más larga actual, en tiempo constante, antes de realizar la búsqueda binaria. Con esta modificación, el algoritmo utiliza como máximo comparaciones en el peor de los casos, lo que es óptimo para un algoritmo basado en comparaciones hasta el factor constante en el término. ^[6] ${\displaystyle O(n\log n).}$ ${\displaystyle X[i]}$ ${\displaystyle n\log _{2}n-n\log _{2}\log _{2}n+O(n)}$ ${\displaystyle O(n)}$

Ejemplo de ejecución

Límites de longitud

Según el teorema de Erdős–Szekeres , cualquier secuencia de números enteros distintos tiene una subsecuencia creciente o decreciente de longitud ^{[7] [8]} Para entradas en las que cada permutación de la entrada es igualmente probable, la longitud esperada de la subsecuencia creciente más larga es aproximadamente ^{[9] [2]} ${\displaystyle n^{2}+1}$ ${\displaystyle n+1.}$ ${\displaystyle 2{\sqrt {n}}.}$

En el límite a medida que se acerca al infinito, el teorema de Baik-Deift-Johansson dice que la longitud de la subsecuencia creciente más larga de una secuencia de elementos permutada aleatoriamente tiene una distribución que se aproxima a la distribución de Tracy-Widom , la distribución del valor propio más grande de una matriz aleatoria en el conjunto unitario gaussiano . ^[10] ${\displaystyle n}$ ${\displaystyle n}$

Algoritmos en línea

La subsecuencia creciente más larga también se ha estudiado en el contexto de algoritmos en línea , en los que los elementos de una secuencia de variables aleatorias independientes con distribución continua -o alternativamente los elementos de una permutación aleatoria- se presentan uno a la vez a un algoritmo que debe decidir si incluye o excluye cada elemento, sin conocimiento de los elementos posteriores. En esta variante del problema, que permite aplicaciones interesantes en varios contextos, es posible idear un procedimiento de selección óptima que, dada una muestra aleatoria de tamaño como entrada, generará una secuencia creciente con una longitud máxima esperada de tamaño aproximadamente ^[11] La longitud de la subsecuencia creciente seleccionada por este procedimiento óptimo tiene una varianza aproximadamente igual a y su distribución límite es asintóticamente normal después del centrado y escalamiento habituales. ^[12] Los mismos resultados asintóticos se mantienen con límites más precisos para el problema correspondiente en el contexto de un proceso de llegada de Poisson. ^[13] Se da un refinamiento adicional en el marco del proceso de Poisson a través de la prueba de un teorema de límite central para el proceso de selección óptimo que se cumple, con una normalización adecuada, en un sentido más completo de lo que cabría esperar. La prueba produce no sólo el teorema de límite funcional "correcto", sino también la matriz de covarianza (singular) del proceso tridimensional que resume todos los procesos que interactúan. ^[14] ${\displaystyle F}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {2n}}.}$ ${\displaystyle {\sqrt {2n}}/3,}$

Véase también

• Anatoly Vershik  – matemático ruso (1933–2024) que estudió las aplicaciones de la teoría de grupos a las subsecuencias crecientes más largas en permutaciones aleatorias. ^[15]
• Subsecuencia alterna más larga
• Subsecuencia común más larga  : problema algorítmico sobre pares de secuencias
• Ordenamiento por paciencia  : algoritmo de ordenamiento: una técnica eficiente para encontrar la longitud de la subsecuencia creciente más larga
• Monoide pláctico  : monoide de números enteros positivos módulo equivalencia de Knuth Pages displaying wikidata descriptions as a fallback: un sistema algebraico definido por transformaciones que preservan la longitud de la subsecuencia creciente más larga

Referencias

1. Aldous, David ; Diaconis, Persi (1999), "Las subsecuencias crecientes más largas: de la clasificación por paciencia al teorema de Baik–Deift–Johansson", Boletín de la Sociedad Matemática Americana , 36 (4): 413–432, doi : 10.1090/S0273-0979-99-00796-X.
2. Romik, Dan (2015). Las sorprendentes matemáticas de las subsecuencias crecientes más largas . doi :10.1017/CBO9781139872003. ISBN 9781107075832.
3. Schensted, C. (1961), "Las subsecuencias crecientes y decrecientes más largas", Revista Canadiense de Matemáticas , 13 : 179–191, doi : 10.4153/CJM-1961-015-3 , MR  0121305.
4. Hunt, J.; Szymanski, T. (1977), "Un algoritmo rápido para calcular las subsecuencias comunes más largas", Communications of the ACM , 20 (5): 350–353, doi : 10.1145/359581.359603 , S2CID  3226080.
5. Golumbic, MC (1980), Teoría algorítmica de grafos y grafos perfectos , Ciencias de la computación y matemáticas aplicadas, Academic Press, pág. 159.
6. Fredman, Michael L. (1975), "Sobre el cálculo de la longitud de las subsecuencias crecientes más largas", Discrete Mathematics , 11 (1): 29–35, doi : 10.1016/0012-365X(75)90103-X.
7. Erdős, Paul ; Szekeres, George (1935), "Un problema combinatorio en geometría", Compositio Mathematica , 2 : 463–470.
8. Steele, J. Michael (1995), "Variaciones sobre el tema de la subsecuencia monótona de Erdős y Szekeres", en Aldous, David ; Diaconis, Persi ; Spencer, Joel ; et al. (eds.), Probabilidad discreta y algoritmos (PDF) , IMA Volumes in Mathematics and its Applications, vol. 72, Springer-Verlag, págs. 111–131.
9. Vershik, AM ; Kerov, CV (1977), "Asintótica de la medida de Plancheral del grupo simétrico y una forma límite para tablas de Young", Dokl. Akad. Nauk SSSR , 233 : 1024–1027.
10. Baik, Jinho; Deift, Percy; Johansson, Kurt (1999), "Sobre la distribución de la longitud de la subsecuencia creciente más larga de permutaciones aleatorias", Journal of the American Mathematical Society , 12 (4): 1119–1178, arXiv : math/9810105 , doi : 10.1090/S0894-0347-99-00307-0.
11. Samuels, Stephen M.; Steele, J. Michael (1981), "Selección secuencial óptima de una secuencia monótona a partir de una muestra aleatoria" (PDF) , Annals of Probability , 9 (6): 937–947, doi : 10.1214/aop/1176994265 , archivado (PDF) desde el original el 30 de julio de 2018
12. Arlotto, Alessandro; Nguyen, Vinh V.; Steele, J. Michael (2015), "Selección en línea óptima de una subsecuencia monótona: un teorema de límite central", Procesos estocásticos y sus aplicaciones , 125 (9): 3596–3622, arXiv : 1408.6750 , doi :10.1016/j.spa.2015.03.009, S2CID  15900488
13. Bruss, F. Thomas ; Delbaen, Freddy (2001), "Reglas óptimas para la selección secuencial de subsecuencias monótonas de longitud máxima esperada", Procesos estocásticos y sus aplicaciones , 96 (2): 313–342, doi : 10.1016/S0304-4149(01)00122-3.
14. Bruss, F. Thomas ; Delbaen, Freddy (2004), "Un teorema de límite central para el proceso de selección óptimo para subsecuencias monótonas de longitud máxima esperada", Procesos estocásticos y sus aplicaciones , 114 (2): 287–311, doi : 10.1016/j.spa.2004.09.002.
15. Romik, Dan (2015). Las sorprendentes matemáticas de las subsecuencias crecientes más largas . Instituto de libros de texto de estadística matemática. Nueva York: Cambridge University Press. ISBN 978-1-107-42882-9.

Enlaces externos

• La subsecuencia creciente más larga del algoritmista
• Subsecuencia creciente más larga simplificada
• Hallar el recuento de las subsecuencias aumentadas más largas