Worldlex Wiki 
En mathématiques combinatoires , une superpermutation de n symboles est une chaîne contenant chaque permutation de n symboles comme sous-chaîne . Si les superpermutations triviales peuvent simplement être composées de toutes les permutations concaténées , elles peuvent aussi être plus courtes (sauf dans le cas trivial où n = 1) car le chevauchement est autorisé. Par exemple, pour n = 2, la superpermutation 1221 contient toutes les permutations possibles (12 et 21), mais la chaîne plus courte 121 contient également les deux permutations.
Il a été démontré que pour 1 ≤ n ≤ 5, la plus petite superpermutation de n symboles a une longueur de 1! + 2! + … + n ! dans l' OEIS ) . Les quatre plus petites superpermutations ont respectivement des longueurs de 1, 3, 9 et 33, formant les chaînes 1, 121, 123121321 et 123412314231243121342132413214321. Cependant, pour n = 5, il existe plusieurs plus petites superpermutations de longueur 153. L'une d'elles est présentée ci-dessous, tandis qu'une autre de même longueur peut être obtenue en permutant tous les 4 et les 5 dans la seconde moitié de la chaîne (après le 2 en gras ) :
12345123 4152341253412354 1231452314253142 35142315 42312453 1243512431524312 5431 2 134 52134251 34215342 13542132 4513241532413524 1325413214532143 52143251 432154321
Pour les cas n > 5, une plus petite superpermutation n'a pas encore été prouvée ni un modèle pour les trouver, mais des bornes inférieures et supérieures ont été trouvées pour celles-ci.
Trouver des superpermutations
L'un des algorithmes les plus courants pour créer une superpermutation d'ordre
Par exemple, une superpermutation d'ordre 3 peut être créée à partir d'une superpermutation à 2 symboles ; en partant de la superpermutation 121 et en la décomposant en les permutations 12 et 21, ces dernières sont copiées et placées comme 12312 et 21321. Elles sont ensuite assemblées pour former 1231221321, et les 2 adjacents identiques au milieu sont fusionnés pour obtenir 123121321, qui est bien une superpermutation d'ordre 3. Cet algorithme produit la superpermutation la plus courte possible pour tout n inférieur ou égal à 5, mais devient de plus en plus longue que la plus courte possible lorsque n augmente au-delà de cette valeur.
Une autre méthode pour trouver des superpermutations consiste à créer un graphe où chaque permutation est un sommet et chaque permutation est reliée à une autre par une arête. Chaque arête est associée à un poids , calculé en déterminant combien de caractères peuvent être ajoutés à la fin d'une permutation (en supprimant le même nombre de caractères au début) pour obtenir l'autre permutation. Par exemple, l'arête de 123 à 312 a un poids de 2 car 123 + 12 = 12312 = 312. Tout chemin hamiltonien dans le graphe ainsi créé est une superpermutation, et le problème de trouver le chemin de poids minimal se ramène au problème du voyageur de commerce . Le premier exemple de superpermutation de poids inférieur à la longueur est donné par l'article [ 3].
bornes inférieures, ou le problème de Haruhi
En septembre 2011, un utilisateur anonyme du forum Science & Math (« /sci/ ») de 4chan a démontré que la plus petite superpermutation de n symboles ( n ≥ 2) a une longueur d'au moins n ! + ( n − 1)! + ( n − 2)! + n − 3. En référence à la série animée japonaise La Mélancolie de Haruhi Suzumiya , et notamment au fait qu'elle a été diffusée à l'origine comme un récit non linéaire , le problème a été présenté sur le forum sous le nom de « Problème de Haruhi » : si vous vouliez regarder les 14 épisodes de la première saison de la série dans tous les ordres possibles, quelle serait la plus courte séquence d'épisodes que vous devriez regarder ? La démonstration de cette borne inférieure a suscité l'intérêt du grand public en octobre 2018, après un tweet de la mathématicienne et informaticienne Robin Houston. Le 25 octobre 2018, Robin Houston, Jay Pantone et Vince Vatter ont publié une version améliorée de cette démonstration dans l' Encyclopédie en ligne des suites d'entiers (OEIS), le premier auteur étant crédité comme « auteur anonyme de 4chan ».
Pour le problème de Haruhi en particulier (cas des 14 symboles), les bornes inférieure et supérieure actuelles sont respectivement de 93 884 313 611 et 93 924 230 411. Cela signifie que regarder la série dans tous les ordres possibles prendrait environ 4,3 millions d’années.
limites supérieures
Le 20 octobre 2018, en adaptant une construction d'Aaron Williams pour construire des chemins hamiltoniens à travers le graphe de Cayley du groupe symétrique , l'auteur de science-fiction et mathématicien Greg Egan a conçu un algorithme pour produire des superpermutations de longueur n ! + ( n −1)! + ( n −2)! + ( n −3)! + n − 3. Jusqu'en 2018, il s'agissait des plus petites superpermutations connues pour n ≥ 7. Cependant, le 1er février 2019, Bogdan Coanda a annoncé avoir trouvé une superpermutation pour n=7 de longueur 5907, soit ( n ! + ( n −1)! + ( n −2)! + ( n −3)! + n − 3) − 1, ce qui constituait un nouveau record. Le 27 février 2019, en s'appuyant sur des idées développées par Robin Houston, Egan a produit une superpermutation de longueur 5906 pour n = 7. L'existence de superpermutations similaires plus courtes pour des valeurs de n > 7 reste une question ouverte. La meilleure borne inférieure actuelle (voir la section ci-dessus) pour n = 7 est toujours de 5884.