Längsta växande delföljd (LIS)

Välj tal ur en lista, från vänster till höger, vart och ett större än det förra. Hur lång kan en sådan kedja bli? Frågan är enkel nog för en gåtbok, och svaret knyter ihop ett kortspel, en klassisk tabell inom dynamisk programmering och ett av de vackraste resultaten om slumpmässiga blandningar.

En rad staplar med olika höjd, där en stigande kedja av dem är markerad i orange från vänster till höger
En rad staplar med olika höjd, där en stigande kedja av dem är markerad i orange från vänster till höger

Problemet

Givet en lista med tal behåller en delföljd några av dem i sin ursprungliga ordning. Den är växande om varje värde är större än det förra. Den längsta växande delföljden, eller LIS, är det längsta sådana urvalet. En lista med n värden har 2ⁿ delföljder, så att kontrollera alla fungerar bara för mycket korta listor.

Tabellen

Låt len[i] vara längden på den längsta växande delföljden som slutar precis vid position i. Den är 1 för värdet ensamt, eller 1 + len[j] för en tidigare position j med mindre värde, beroende på vilket som är störst. Varje position tittar tillbaka på alla tidigare, så tabellen kräver n·(n − 1)/2 jämförelser. Svaret är det största len[i], och om man antecknar vilket j som gav varje len[i] kan man läsa delföljden baklänges.

Ett exempel

Ta 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Position för position är längderna 1, 2, 1, 1, 3, 2, 3, 4, 3 och 5: 20 förlänger 3, 10; 4 förlänger 3; 6 förlänger 4, 7 förlänger 6 och 9 förlänger 7. Läser man baklänges från 9 får man 3, 4, 6, 7, 9, en växande delföljd med längd 5.

Snabbare: patienssortering

Dela ut värdena som kort i högar: varje värde läggs på högen längst till vänster vars översta kort inte är mindre än värdet, eller börjar en ny hög till höger. Antalet högar är längden på LIS. Eftersom de översta korten i högarna alltid är sorterade kan rätt hög hittas med binärsökning, så hela metoden tar O(n log n) steg. Den är uppkallad efter patiensen den påminner om.

Lite matematik

År 1935 bevisade Paul Erdős och George Szekeres att varje lista med n² + 1 olika tal har en växande eller en avtagande delföljd med längd n + 1. Stanislaw Ulam frågade 1961 hur lång LIS är för en slumpmässig blandning av n tal. Svaret, nära 2√n för stora n, avgjordes 1977 av Anatoly Vershik och Sergei Kerov och av Ben Logan och Larry Shepp, och 1999 fann Jinho Baik, Percy Deift och Kurt Johansson den exakta formen på dess fluktuationer: Tracy–Widom-fördelningen från teorin om slumpmatriser.

Paul Erdős vid ett studentseminarium i Budapest 1992. År 1935 bevisade han och George Szekeres att varje lista med n² + 1 olika tal har en växande eller avtagande delföljd av längd n + 1.
Paul Erdős vid ett studentseminarium i Budapest 1992. År 1935 bevisade han och George Szekeres att varje lista med n² + 1 olika tal har en växande eller avtagande delföljd av längd n + 1.
Porträtt av Stanisław Ulam
Porträtt av Stanisław Ulam

Utforska

Öppna appen och tryck på Steg. Den orange kolumnen är positionen som räknas ut och den blå kolumnen den tidigare position den jämförs med. Raden Längd växer när längre kedjor hittas, raden Kommer efter minns var de kom ifrån, och på slutet läses svaret baklänges i orange och visas under tabellen.

Ofta ställda frågor

Vilken tidskomplexitet har LIS?

O(n²) med tabellen, eftersom varje position tittar på alla tidigare, och O(n log n) med patienssortering och binärsökning. Båda behöver O(n) minne.

Hur hittar jag den längsta icke-avtagande delföljden?

Låt ett värde komma efter ett lika stort: jämför med ≤ i stället för <. Kryssa i Tillåt lika värden i appen. Med patienssortering lägger du varje värde på högen längst till vänster vars översta kort är strikt större.

Vad är den längsta avtagande delföljden?

Samma problem med jämförelsen omvänd, eller LIS för listan där varje värde har bytt tecken. Enligt Erdős–Szekeres sats har en tillräckligt lång lista alltid en lång växande eller en lång avtagande delföljd.

Hur lång är LIS för en slumpmässig lista?

För en slumpmässig blandning av n olika tal ungefär 2√n för stora n. Korrektionen växer som sjätteroten ur n, så för tusen tal är medelvärdet omkring 58, lite under 2√1000 ≈ 63.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova den längsta växande delföljden