Længste voksende delfølge (LIS)
Vælg tal fra en liste, fra venstre mod højre, hvert større end det forrige. Hvor lang kan sådan en kæde blive? Spørgsmålet er enkelt nok til en gådebog, og svaret forbinder et kortspil, en klassisk tabel fra dynamisk programmering og et af de smukkeste resultater om tilfældige blandinger.
Problemet
Givet en liste af tal beholder en delfølge nogle af dem i deres oprindelige rækkefølge. Den er voksende, hvis hver værdi er større end den forrige. Den længste voksende delfølge, eller LIS, er det længste sådanne udvalg. En liste med n værdier har 2ⁿ delfølger, så at tjekke dem alle virker kun for meget korte lister.
Tabellen
Lad len[i] være længden af den længste voksende delfølge, der slutter præcis ved position i. Den er 1 for værdien alene eller 1 + len[j] for en tidligere position j med en mindre værdi, alt efter hvad der er størst. Hver position ser tilbage på alle tidligere, så tabellen kræver n·(n − 1)/2 sammenligninger. Svaret er det største len[i], og hvis man noterer, hvilket j der gav hvert len[i], kan man læse delfølgen baglæns.
Et eksempel
Tag 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Position for position er længderne 1, 2, 1, 1, 3, 2, 3, 4, 3 og 5: 20 forlænger 3, 10; 4 forlænger 3; 6 forlænger 4, 7 forlænger 6, og 9 forlænger 7. Læser man baglæns fra 9, får man 3, 4, 6, 7, 9, en voksende delfølge af længde 5.
Hurtigere: kabalesortering
Del værdierne ud som kort i bunker: hver værdi lægges på den bunke længst til venstre, hvis øverste kort ikke er mindre end den, eller starter en ny bunke til højre. Antallet af bunker er længden af LIS. Fordi de øverste kort i bunkerne altid er sorteret, kan den rigtige bunke findes med binær søgning, så hele metoden tager O(n log n) trin. Den er opkaldt efter den kabale, den minder om (på engelsk patience).
Lidt matematik
I 1935 beviste Paul Erdős og George Szekeres, at enhver liste af n² + 1 forskellige tal har en voksende eller en aftagende delfølge af længde n + 1. Stanislaw Ulam spurgte i 1961, hvor lang LIS er for en tilfældig blanding af n tal. Svaret, tæt på 2√n for store n, blev fundet i 1977 af Anatoly Vershik og Sergei Kerov og af Ben Logan og Larry Shepp, og i 1999 fandt Jinho Baik, Percy Deift og Kurt Johansson den præcise form på udsvingene: Tracy–Widom-fordelingen fra teorien om tilfældige matricer.
Udforsk det
Åbn appen, og tryk på Trin. Den orange søjle er den position, der regnes ud, og den blå søjle er den tidligere position, den sammenlignes med. Rækken Længde vokser, efterhånden som længere kæder findes, rækken Kommer efter husker, hvor de kom fra, og til sidst læses svaret baglæns i orange og vises under tabellen.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten for LIS?
O(n²) med tabellen, fordi hver position ser på alle tidligere, og O(n log n) med kabalesortering og binær søgning. Begge kræver O(n) hukommelse.
Hvordan finder jeg den længste ikke-aftagende delfølge?
Lad en værdi komme efter en lige så stor værdi: sammenlign med ≤ i stedet for <. Sæt flueben ved Tillad ens værdier i appen. Ved kabalesortering lægges hver værdi på den bunke længst til venstre, hvis øverste kort er strengt større.
Hvad er den længste aftagende delfølge?
Det samme problem med sammenligningen vendt om, eller LIS for listen, hvor hver værdi har skiftet fortegn. Ifølge Erdős–Szekeres' sætning har en lang nok liste altid en lang voksende eller en lang aftagende delfølge.
Hvor lang er LIS for en tilfældig liste?
For en tilfældig blanding af n forskellige tal tæt på 2√n for store n. Korrektionen vokser som sjetteroden af n, så for tusind tal er gennemsnittet omkring 58, lidt under 2√1000 ≈ 63.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv den længste voksende delfølge