Superpermutations

2. Superpermutation Minimale

L'algorithme récursif suivant permet de générer une superpermutation sur un alphabet \Sigma_n = \{1,...,n\}.

SuperP(L, m, i)
  if(i == 0) 
    return L
  P = AllShuffle(L, m-1)
  SP = []
  Pour chaque élément e de P faire :
    SP = SP + e + [m] + e
  SP = ExtractOverlap(SP)
  return SuperP(SP, (m+1), (i-1))

L'entier i correspond à l'alphabet \Sigma_i et L est une liste de superpermutation calculée récursivement.

Idée : on part d'une superpermutation de \Sigma_2 : 121, que l'on découpe en les deux permutations lues dans l'ordre :

    \[ 12 \quad 21. \]

On double chacune de ces chaînes en intercalant l'élément que l'on rajoute à \Sigma_2 pour obtenir \Sigma_3, donc 3 :

    \[ 12-3-12\quad 21-3-21\]

puis l'on fusionne les deux mots obtenus en superposant au centre les caractères partagés entre les deux chaînes :

    \[ 12321321. \]

On peut répéter le processus sur cette nouvelle superpermutation de \Sigma_3 pour obtenir une superpermutation de \Sigma_4, etc.

On peut montrer par induction structurelle sur n que la taille de la superpermutation ainsi produite est

    \[ T_n = \sum_{k=1}^{n}k!. \]

Il a été conjecturé que cet algorithme permettrait de construire une superpermutation la plus petite possible.

Pour en revenir à notre problème initial, on avait calculé qu'il fallait

    \[ 14\times 14!\times 20 = 464\,420 \text{ si\`ecles.} \]

pour regarder naïvement les 14 épisodes de notre série dans tous les ordres possibles. Grâce à cet algorithme, nous pouvons trouver un ordre nous permettant de regarder les épisodes de cette série dans tous les ordres possibles en

    \[ 20 \times\left(\sum_{k=1}^{14}k!\right) \approx 35\,741\text{ si\`ecles.}\]

Si l'on gagne un facteur 10 dans le temps de visionnage, cela reste encore bien déraisonnable. Mais est-ce bien la taille de la plus petite superpermutation de lettres, ou peut-on encore gagner du temps ?

À défaut de prouver la conjecture, des mathématiciens ont essayé de la vérifier par « brute-force » sur des alphabets de petite taille. Il suffit de générer tous les mots de taille plus petite que la taille conjecturée. Par exemple, sur un alphabet \Sigma_4 de taille 4, la taille d'une des plus petites superpermutation de \Sigma_4 que l'on connaisse est T_4=33. Il s'agit donc de chercher s'il existe (ou non) une superpermutation de \Sigma_4 plus petite.

Le nombre de mots de k lettres sur un alphabet de 4 symboles est 4^k, ainsi, le nombre de mots ayant moins de 33 lettres sur un alphabet de 4 symboles est

    \[ \sum_{k=1}^{33}4^{k} \;\approx\; 9,8\times 10^{18}. \]

On peut généraliser : sur un alphabet de n symboles, le nombre de mots de taille inférieure à T_n est :

    \[ \sum_{k=1}^{T_n}n^{k}. \]

Bien sûr, les algorithmes mis en jeu sont optimisés pour ne pas considérer tous les mots qui ne ressemblent pas, de loin, à une superpermutation de manière à gagner du temps. De cette manière, il a été prouvé que la conjecture est vraie pour n \leqslant 5.

Le 22 août 2014, le mathématicien Robin Houston a découvert une superpermutation contredisant la conjecture pour n = 6. En effet, le mot suivant :

12345612345162345126345123645132645136245136425136452136451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654132654312645316243516243156243165243162543162453164253146253142653142563142536142531645231465231456231452631452361452316453216453126435126431526431256432156423154623154263154236154231654231564213564215362415362145362154362153462135462134562134652134625134621536421563421653421635421634521634251634215643251643256143256413256431265432165432615342613542613452613425613426513426153246513246531246351246315246312546321546325146325416325461325463124563214563241563245163245613245631246532146532416532461532641532614532615432651436251436521435621435261435216435214635214365124361524361254361245361243561243651423561423516423514623514263514236514326541362541365241356241352641352461352416352413654213654123

est une superpermutation de \Sigma = \{1,2,3,4,5,6\} de taille 872 alors que T_6 = 873. On a ainsi prouvé que T_n ne donnait pas la taille de la superpermutation minimale dès que n\geqslant5.

Le problème de la superpermutation minimale, tant sa construction que sa taille, est encore ouvert aujourd'hui.

1 Cliquer pour recommander cet article