Superpermutazione
In matematica combinatoria, una superpermutazione di n simboli è una stringa che contiene tutte le permutazioni dei suoi simboli come sottostringa.
Si sa che per 1 ≤ n ≤ 5 le superpermutazioni minimali di n simboli, cioè quelle di lunghezza minore possibile, hanno lunghezza 1! + 2! + … + n! [1]. Le prime cinque superpermutazioni minimali hanno pertanto lunghezza rispettiva 1, 3, 9, 33, e 153, e sono date dalle stringhe 1, 121, 123121321, 123412314231243121342132413214321, e:
123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321
Per n ≥ 6 non è nota qual è la lunghezza minima: è possibile scendere sotto il valore dato dalla formula suindicata, come mostrato per la prima volta nel 2014 da Robin Houston[2].
Limiti superiori e inferiori
Limite inferiore
Nel settembre 2011 un utente anonimo del sito di immagini 4chan dimostrò che la superpermutazione minimale di n simboli (per n ≥ 2) ha lunghezza almeno n! + (n-1)! + (n-2)! + n - 3.[3] A ottobre 2018 Houston ha riportato in auge il problema[4][5]. Il 25 ottobre 2018 Houston, insieme a Jay Pantone e Vince Vatter, hanno pubblicato una nuova versione della dimostrazione su OEIS.[6]
Limite superiore
Il 20 ottobre 2018, adattando una procedura di Aaron Williams per costruire un cammino hamiltoniano sul grafo di Cayley di un gruppo simmetrico,[7] lo scrittore di fantascienza Greg Egan ha sviluppato un algoritmo che produce superpermutazioni di lunghezza n! + (n-1)! + (n-2)! + (n-3)! + n - 3.[8][9] Al momento questi sono i migliori risultati noti per n ≥ 7.
Note
Altri progetti
Wikimedia Commons contiene immagini o altri file su Superpermutazione
Collegamenti esterni
- (EN) The Minimal Superpermutation Problem - Nathaniel Johnston's blog
- (EN) James Grime, Superpermutations - Numberphile, su YouTube. URL consultato il 28 ottobre 2018.