Sottosequenza crescente più lunga (LIS)

Scegli numeri da una lista, da sinistra a destra, ognuno più grande del precedente. Quanto può diventare lunga una catena così? La domanda è abbastanza semplice per un libro di enigmi, e la sua risposta collega un gioco di carte, una classica tabella di programmazione dinamica e uno dei risultati più belli sui mescolamenti casuali.

Una fila di barre di altezze diverse, con una catena crescente di esse evidenziata in arancione, da sinistra a destra
Una fila di barre di altezze diverse, con una catena crescente di esse evidenziata in arancione, da sinistra a destra

Il problema

Data una lista di numeri, una sottosequenza ne tiene alcuni nel loro ordine originale. È crescente se ogni valore è più grande del precedente. La sottosequenza crescente più lunga, o LIS, è la scelta di questo tipo più lunga. Una lista di n valori ha 2ⁿ sottosequenze, quindi controllarle tutte funziona solo per liste molto corte.

La tabella

Sia len[i] la lunghezza della sottosequenza crescente più lunga che finisce esattamente nella posizione i. Vale 1 per il valore da solo, oppure 1 + len[j] per una posizione precedente j con un valore più piccolo, scegliendo il più grande. Ogni posizione guarda indietro a tutte quelle precedenti, quindi la tabella richiede n·(n − 1)/2 confronti. La risposta è il len[i] più grande, e annotare quale j ha dato ogni len[i] permette di rileggere la sottosequenza.

Un esempio

Prendi 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Posizione per posizione le lunghezze sono 1, 2, 1, 1, 3, 2, 3, 4, 3 e 5: il 20 allunga 3, 10; il 4 allunga il 3; il 6 allunga il 4, il 7 il 6 e il 9 il 7. Rileggendo dal 9 si ottiene 3, 4, 6, 7, 9, una sottosequenza crescente di lunghezza 5.

Un modo più veloce: il patience sorting

Distribuisci i valori come carte in pile: ogni valore va sulla pila più a sinistra la cui cima non è più piccola di lui, oppure inizia una nuova pila a destra. Il numero di pile è la lunghezza della LIS. Poiché le cime delle pile sono sempre ordinate, la pila giusta si trova con la ricerca binaria, quindi l'intero metodo richiede O(n log n) passi. Prende il nome dal solitario di carte (in inglese patience) a cui somiglia.

Un po' di matematica

Nel 1935 Paul Erdős e George Szekeres dimostrarono che ogni lista di n² + 1 numeri diversi ha una sottosequenza crescente o decrescente di lunghezza n + 1. Nel 1961 Stanislaw Ulam si chiese quanto è lunga la LIS di un mescolamento casuale di n numeri. La risposta, vicina a 2√n per n grande, fu trovata nel 1977 da Anatoly Vershik e Sergei Kerov e da Ben Logan e Larry Shepp, e nel 1999 Jinho Baik, Percy Deift e Kurt Johansson trovarono la forma esatta delle sue fluttuazioni: la distribuzione di Tracy–Widom della teoria delle matrici casuali.

Paul Erdős a un seminario per studenti a Budapest nel 1992. Nel 1935 lui e George Szekeres dimostrarono che ogni lista di n² + 1 numeri distinti ha una sottosequenza crescente o decrescente di lunghezza n + 1.
Paul Erdős a un seminario per studenti a Budapest nel 1992. Nel 1935 lui e George Szekeres dimostrarono che ogni lista di n² + 1 numeri distinti ha una sottosequenza crescente o decrescente di lunghezza n + 1.
Ritratto di Stanisław Ulam
Ritratto di Stanisław Ulam

Provalo

Apri l'app e premi Passo. La colonna arancione è la posizione che si sta calcolando e la colonna blu la posizione precedente con cui viene confrontata. La riga Lunghezza cresce man mano che si trovano catene più lunghe, la riga Viene dopo ricorda da dove vengono, e alla fine la risposta viene riletta in arancione e mostrata sotto la tabella.

Domande frequenti

Qual è la complessità temporale della LIS?

O(n²) con la tabella, perché ogni posizione guarda tutte quelle precedenti, e O(n log n) con il patience sorting e la ricerca binaria. Entrambi richiedono O(n) di memoria.

Come trovo la sottosequenza non decrescente più lunga?

Permetti a un valore di seguire un valore uguale: confronta con ≤ invece che con <. Nell'app, spunta Consenti valori uguali. Con il patience sorting, metti ogni valore sulla pila più a sinistra la cui cima è strettamente più grande.

Che cos'è la sottosequenza decrescente più lunga?

Lo stesso problema con il confronto invertito, oppure la LIS della lista con ogni valore cambiato di segno. Per il teorema di Erdős–Szekeres, una lista abbastanza lunga ha sempre una lunga sottosequenza crescente o una lunga sottosequenza decrescente.

Quanto è lunga la LIS di una lista casuale?

Per un mescolamento casuale di n numeri diversi, circa 2√n per n grande. La correzione cresce come la radice sesta di n, quindi per mille numeri la media è circa 58, un po' meno di 2√1000 ≈ 63.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova la sottosequenza crescente più lunga