Längste streng ansteigende Folge

Die Suche nach einer länger streng steigenden Teilfolge in einer endlichen Folge ist ein klassisches Problem bei Algorithmen . Dieses Problem kann in der Zeit O ( n log n ) in der Länge der Sequenz gelöst werden.

Beschreibung

Die Eingabe für das Problem ist eine endliche Folge x 1 , ..., x n . Formal ist das Ziel eine finden Teilfolge streng monoton wachsend von der Suite , eine zunehmende Funktion ⟦1, L ⟧ → ⟦1, n ⟧ für die größte Länge L möglich. $(x _ {{\ varphi (i)}}) _ {{i \ leq L}}$ $(x_ {i}) _ {{i \ leq n}}$ $\ varphi$

Zum Beispiel hat die Sequenz (6, 1, 4, 9, 5, 11) streng ansteigende Teilsequenzen der Länge 4, aber keine der Länge 5. Eine länger streng ansteigende Teilsequenz ist (1, 4, 9, 11), erhalten durch Nehmen Sie die Elemente in Position 2, 3, 4 und 6 der Anfangssequenz. Im Allgemeinen ist die Lösung nicht eindeutig. Hier ist eine andere Lösung (1, 4, 5, 11).

Dieses Problem wird manchmal mit dem Akronym LIS für die am längsten zunehmende Teilsequenz bezeichnet .

Algorithmus

Der folgende dynamische Programmieralgorithmus löst das Problem der am längsten wachsenden Teilsequenz in der quasi-linearen Zeit O ( n log n ). Es werden nur Tabellen und eine dichotome Suchfunktion verwendet . Es verarbeitet die Elemente der Sequenz der Reihe nach und speichert die längste streng ansteigende Teilsequenz, die bisher gefunden wurde, und andere kürzere Teilsequenzen, deren letztes Element jedoch kleiner ist (daher möglicherweise einfacher mit den folgenden Elementen zu vervollständigen). Die Elemente der Sequenz werden mit X [1], X [2], ..., X [N] bezeichnet. Nach der Behandlung von X [ i ] werden die folgenden Invarianten verifiziert:

M [ j ] enthält eine Position k, so dass X [ k ] der kleinstmögliche Wert des letzten Elements einer streng ansteigenden Teilfolge von X [1], ..., X [ i ] mit genau j Elementen ist.
P [ k ] enthält den Index des Vorgängers von X [ k ] in einer längeren, streng ansteigenden Teilsequenz, die in Position k endet .

Der Algorithmus behält in einer Variablen L die Länge der längsten streng ansteigenden Teilsequenz, die gefunden wurde.

Zu jeder Zeit nimmt die Sequenz X [M [1]], X [M [2]], ..., X [M [L]] zu. Wenn tatsächlich eine streng zunehmende Teilfolge der Länge i > 1 existiert, die in Position M [ i ] endet , dann existiert eine streng zunehmende Teilfolge der Länge i -1, die mit einem niedrigeren Wert endet. Mit zunehmender Sequenz ist es möglich, in dieser Sequenz eine dichotome Suche durchzuführen. Achtung: Im Allgemeinen nimmt die Folge der Indizes M [1], M [2], ..., M [L] nicht zu, daher X [M [1]], X [M [2]], .. ., X [M [L]] ist keine Teilfolge von X [1], ..., X [L] (daher keine Lösung des Problems).

Beschreibung des Algorithmus:

Entrée : X, un tableau indicé de 1 à n. Sortie : L, longueur de la plus longue sous-suite strictement croissante de X. P, tableau de prédécesseurs permettant de reconstruire explicitement la suite. P = tableau indicé de 1 à n M = tableau indicé de 0 à n L = 0 M[0] = 0 pour i = 1, 2, ..., n : par recherche dichotomique, trouver le plus grand entier j tel que 1 ≤ j ≤ L et X[M[j]] < X[i] ou définir j = 0 s'il n'en existe aucun. P[i] = M[j] si j == L ou X[i] < X[M[j + 1]] : M[j + 1] = i L = max(L, j + 1)

Die Elemente der Teilsequenz können ausgehend vom letzten Element X [M [L]] berechnet und dann in die Tabelle P der Vorgänger aufgenommen werden: Das vorletzte Element ist X [P [M [L]], das vorletzte ist X [P [P [M [L]]] und so weiter.

Bei jeder Schleifenrunde ist die teuerste Operation die dichotome Suche der Komplexität O (log n ). Die Gesamtausführungszeit des Algorithmus beträgt daher O ( n log n ).

Verknüpfungen mit der längsten gemeinsamen Teilsequenz

Das Problem der längsten wachsende Subsequenz zu der der verbunden ist längsten Subsequenz gemeinsam zu zwei Sequenzen, für die es einen Algorithmus der Auflösung durch existiert dynamische Programmierung der quadratischen Komplexität: vorausgesetzt , dass das Alphabet auf , welche Kanäle definiert , mit einer zur Verfügung gestellt wird , um Beziehung Die am längsten ansteigende Teilfolge einer Folge S ist die längste gemeinsame Teilfolge in S und T , wobei T durch Sortieren von S erhalten wird .

Umgekehrt kann das Problem der längsten Teilfolge, die zwei Sequenzen S [1], S [2], ..., S [n] und T [1], T [2], ..., T [m] gemeinsam ist werden reduziert , um das Problem der längsten zunehmende Teilfolge. Dazu bezeichnen wir mit A [ x ] die Liste der Indizes der Elemente von S als x in absteigender Reihenfolge. Wenn i [1], i [2], ..., i [k] eine länger streng ansteigende Teilsequenz der Sequenz ist, die durch Verketten von A [T [1]], ..., A [T [m]] erhalten wird , dann S [i [1]], ..., S [i [k]] ist eine längste gemeinsame Subsequenz in S und T . Die Größe der durch Verkettung erhaltenen Sequenz beträgt höchstens nm , jedoch nur m, wenn die erste Sequenz kein doppeltes Element enthält. Somit ergibt die Reduktion eine relativ effiziente Methode zur Lösung des längsten gemeinsamen Teilsequenzproblems in häufigen Sonderfällen.

Längste streng ansteigende Folge einer Permutation

Definition

Wir bezeichnen durch die symmetrische Gruppe von Permutationen von ⟦1, n⟧. Sei eine Permutation, wir identifizieren die am längsten ansteigende Folge der Permutation mit der am längsten ansteigenden Teilfolge von und sei ihre Länge. Zeigt auch die Anzahl der Stapel in der Patience-Sortierung an . ${\ displaystyle {\ mathfrak {S}} _ {n}}$ ${\ displaystyle \ sigma \ in {\ mathfrak {S}} _ {n}}$ ${\ displaystyle (\ sigma (i)) _ {1 \ leq i \ leq n}}$ ${\ displaystyle \ ell (\ sigma)}$ ${\ displaystyle \ ell (\ sigma)}$

Satz von Baik-Deift-Johansson

Sei eine ganze Zahl ungleich Null und das Haar-Maß (einheitliche Wahrscheinlichkeit) dann für jedes reelle $nicht$ ${\ displaystyle \ mathbb {P} _ {n}}$ ${\ displaystyle {\ mathfrak {S}} _ {n}}$ $s$

limnicht→∞P.nicht((ℓ((σ)- -2nichtnicht16<s)=F.2((s){\ displaystyle \ lim _ {n \ to \ infty} \ mathbb {P} _ {n} \ left ({\ frac {\ ell (\ sigma) -2 {\ sqrt {n}}} {n ^ {\ frac {1} {6}}}} <s \ right) = F_ {2} (s)} ${\ displaystyle \ lim _ {n \ to \ infty} \ mathbb {P} _ {n} \ left ({\ frac {\ ell (\ sigma) -2 {\ sqrt {n}}} {n ^ {\ frac {1} {6}}}} <s \ right) = F_ {2} (s)}$

Wo ist die kumulative Funktion der Tracy-Widom-Verteilung für . ${\ displaystyle F_ {2}}$ ${\ displaystyle \ beta = 2}$

Anmerkungen und Referenzen

(de) Dieser Artikel stammt teilweise oder vollständig aus dem englischen Wikipedia- Artikel " Längste zunehmende Teilsequenz " ( siehe Autorenliste ) .

(in) Craige Schensted , " Längste zunehmende und abnehmende Teilfolgen " , Canadian Journal of Mathematics , vol. 13,1961, p. 179-191 ( DOI 10.4153 / CJM-1961-015-3 , Math Reviews 0121305 ).
(in) Dan Gusfield , Algorithmen sind Strings, Bäume und Sequenzen: Informatik und Computational Biology , Cambridge University Press ,Mai 1997534 p. ( ISBN 978-0-521-58519-4 , online lesen ) , „Verfeinern von Änderungen und Ausrichtungen von Kernzeichenfolgen“ , S. 22 . 290-292.
" American Mathematical Society " ( DOI 10.1090 / s0273-0979-99-00796-x , abgerufen am 17. Januar 2018 )
" American Mathematical Society " ( DOI 10.1090 / s0894-0347-99-00307-0 , abgerufen am 17. Januar 2018 )

Siehe auch

Dan Romik, Die überraschende Mathematik der am längsten zunehmenden Folgen, Cambridge University Press,2015353 p. ( ISBN 9781107428829 ).
Längste gemeinsame Untersuite
Die längste streng abnehmende Teilsequenz entspricht dem Problem der Clique in einem Permutationsgraphen .