Subsecuencia creciente más larga

problema de informática

En informática , el problema de 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 diversas disciplinas relacionadas con las matemáticas , incluida 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 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

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

Relaciones con otros problemas algorítmicos

El problema de subsecuencia creciente más largo está estrechamente relacionado con el problema de subsecuencia común más largo , que tiene una solución de programación dinámica de tiempo cuadrática : la subsecuencia creciente más larga de una secuencia es la subsecuencia común más larga de y donde está 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 puede hacerse 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).}$

La camarilla 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 (suponiendo 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, se pueden utilizar algoritmos de subsecuencia creciente más larga para resolver el problema de camarilla de manera eficiente en gráficos de permutación. ^[5]

En la correspondencia de Robinson-Schensted entre permutaciones y cuadros de Young , la longitud de la primera fila del cuadro 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 creciente más larga de la permutación. subsecuencia decreciente. ^[3]

Algoritmos eficientes

El algoritmo que se describe a continuación resuelve eficientemente el problema de subsecuencia creciente más larga con matrices 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 número entero y valores en dos matrices: ${\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 hay una subsecuencia creciente de longitud que termina en en el rango Explícitamente, supongamos que denota el conjunto de todos los índices tales que existe una subsecuencia creciente de longitud que termina en Entonces es el índice en para que se minimiza; es decir, 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, el algoritmo solo los utiliza). Si sin embargo se usa/definió entonces (y además, en la iteración también se mantendrá). no está definido ya que las secuencias de longitud no tienen índice final ( puede tener 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 siguiente algoritmo utiliza numeración de base cero , para mayor claridad se completa con lo que no se utiliza para que corresponda 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]}$

Tenga en cuenta que, en cualquier punto del algoritmo, la secuencia

$${\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 positivo más pequeño l ≤ L // tal que X[M[l]] > X[i] lo = 1 hola = L + 1 mientras lo < hola: mid = lo + piso((hola-lo)/2) // lo <= mid < hola si X[M[medio]] >= X[i] hola = medio else : // si X[M[mediado]] < 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 newL-1 P[i] = M[nuevaL-1] M[nuevaL] = yo  si nuevoL > L: // Si encontramos una subsecuencia más larga que cualquiera que hayamos encontrado // encontrado todavía, actualiza L L = nuevoL// Reconstruir la subsecuencia creciente más larga// Consta de 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]devoluciones​

Debido a que el algoritmo realiza una única búsqueda binaria por elemento de secuencia, su tiempo total se puede expresar utilizando la notación O grande, ya que 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 cual 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)}$

Ejecución de ejemplo

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 cuando 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 secuencia aleatoria matriz 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 por uno a un algoritmo que debe decidir si incluir o excluir cada elemento, sin conocer los elementos posteriores. En esta variante del problema, que permite aplicaciones interesantes en varios contextos, es posible diseñar un procedimiento de selección óptimo que, dada una muestra aleatoria de tamaño como entrada, generará una secuencia creciente con la longitud máxima esperada de tamaño aproximadamente ^{[11 ]} La longitud de la subsecuencia creciente seleccionada mediante este procedimiento óptimo tiene una varianza aproximadamente igual a y su distribución límite es asintóticamente normal después del centrado y escalado habituales. ^[12] Los mismos resultados asintóticos son válidos con límites más precisos para el problema correspondiente en el contexto de un proceso de llegada de Poisson. ^[13] Un mayor refinamiento en el proceso de Poisson se logra mediante la demostración 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 arroja no sólo el teorema del 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,}$

Ver 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 en pares de secuencias
• Clasificación por paciencia  : algoritmo de clasificación: una técnica eficaz para encontrar la longitud de la subsecuencia creciente más larga
• Monoide plactico  - monoide de enteros positivos módulo de equivalencia 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), "Subsecuencias crecientes más largas: de la clasificación por paciencia al teorema de Baik-Deift-Johansson", Boletín de la Sociedad Matemática Estadounidense , 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), "Subsecuencias crecientes y decrecientes más largas", Canadian Journal of Mathematics , 13 : 179–191, doi : 10.4153/CJM-1961-015-3 , MR  0121305.
4. Caza, 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 de grafos algorítmicos y gráficos perfectos , informática y matemáticas aplicadas, Academic Press, p. 159.
6. Fredman, Michael L. (1975), "Sobre el cálculo de la longitud de las subsecuencias crecientes más largas", Matemáticas discretas , 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.), Algoritmos y probabilidad discreta (PDF) , Volúmenes IMA en Matemáticas y sus aplicaciones, vol. 72, Springer-Verlag, págs. 111-131.
9. Vershik, soy ; Kerov, CV (1977), "Asintóticas de la medida de Plancheral del grupo simétrico y una forma limitante para cuadros de Young", Dokl. Akád. Nauk SSSR , 233 : 1024-1027.
10. Baik, Jinho; Deft, 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, Esteban. METRO.; 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) ) del original el 30 de julio de 2018
12. Arlotto, Alessandro; Nguyen, Vinh V.; Steele, J. Michael (2015), "Selección óptima en línea de una subsecuencia monótona: un teorema del 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 del 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). "La sorprendente matemática 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 algoritmo
• Subsecuencia creciente más larga simplificada
• Encontrar el recuento de subsecuencias aumentadas más largas