Superpermutace - Superpermutation - Wikipedia

Distribuce permutací v superpermutaci se 3 symboly.

v kombinační matematika, a superpermutace na n symboly je a tětiva který obsahuje každý permutace z n symboly jako a podřetězec. Zatímco triviální superpermutace mohou být jednoduše tvořeny každou permutací uvedenou společně, superpermutace mohou být také kratší (kromě triviálního případu n = 1) protože překrytí je povoleno. Například v případě n = 2, superpermutace 1221 obsahuje všechny možné permutace (12 a 21), ale kratší řetězec 121 také obsahuje obě permutace.

Ukázalo se, že pro 1 ≤ n ≤ 5, nejmenší zapnutá superpermutace n symboly má délku 1! + 2! +… + n! (sekvence A180632 v OEIS ). První čtyři nejmenší superpermutace mají příslušné délky 1, 3, 9 a 33, které tvoří řetězce 1, 121, 123121321 a 123412314231243121342132413214321. Avšak pro n = 5, existuje několik nejmenších superpermutací majících délku 153. Jedna taková superpermutace je zobrazena níže, zatímco další stejné délky lze získat přepnutím všech čtyřek a pětek ve druhé polovině řetězce (po tučně 2):[1]

123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321

Pro případy n > 5 dosud nebyla prokázána nejmenší superpermutace ani vzor k jejich nalezení, ale byla pro ně nalezena dolní a horní hranice.

Hledání superpermutací

Schéma vytvoření superpermutace se 3 symboly ze superpermutace se 2 symboly.

Jeden z nejběžnějších algoritmů pro vytvoření superpermutace řádu je rekurzivní algoritmus. Nejprve superpermutace řádu je rozdělena na jednotlivé permutace v pořadí, v jakém se objevily při superpermutaci. Každá z těchto permutací je poté umístěna vedle jejich kopie s nmezi dvě kopie byl přidán tento symbol. Nakonec je každá výsledná struktura umístěna vedle sebe a všechny sousední identické symboly jsou sloučeny.[2]

Například superpermutace řádu 3 může být vytvořena z jednoho se 2 symboly; počínaje superpermutací 121 a jejím rozdělením na permutace 12 a 21, jsou permutace zkopírovány a umístěny jako 12312 a 21321. Jsou umístěny společně, aby vytvořily 1231221321, a identické sousední 2s uprostřed jsou sloučeny, aby vytvořily 123121321, což je skutečně superpermutací řádu 3. Výsledkem tohoto algoritmu je nejkratší možná superpermutace pro všechny n menší nebo roven 5, ale stává se čím dál delší než nejkratší možný n zvýšit nad to.[2]

Další způsob hledání superpermutací spočívá ve vytvoření a graf kde každá permutace je a vrchol a každá permutace je spojena hranou. Každá hrana má a hmotnost spojené s tím; váha se vypočítá podle toho, kolik znaků lze přidat na konec jedné permutace (upuštění stejného počtu znaků od začátku), což má za následek druhou permutaci.[2] Například hrana od 123 do 312 má váhu 2, protože 123 + 12 = 12312 = 312. Libovolná hamiltonovská cesta prostřednictvím vytvořeného grafu je superpermutace a problém najít cestu s nejmenší váhou se stává formou problém obchodního cestujícího. První instance superpermutace menší než délka byl nalezen pomocí počítačového vyhledávání této metody Robinem Houstonem.[3]

Dolní a horní mez

Algoritmus pro nalezení nejmenší superpermutace pro 6 nebo více symbolů není dosud vyřešen. Několik důkazů však silných postupně zmenšilo horní a dolní mez problému v průběhu času.

Dolní hranice nebo problém Haruhi

V září 2011 anonymní plakát k časopisu Science & Math („/ sci /“) prkno z 4chan dokázal, že nejmenší superpermutace byla zapnuta n symboly (n ≥ 2) má alespoň délku n! + (n−1)! + (n−2)! + n − 3.[4] S odkazem na Japonce anime série Melancholie Haruhi Suzumiya, byl problém zobrazen na grafické desce jako „The Haruhi Problem“: pokud byste chtěli sledovat 14 epizod první sezóny seriálu v jakémkoli možném pořadí, jaký by byl nejkratší sled epizod, který byste potřebovali sledovat?[5] Důkaz pro tuto dolní hranici přišel k obecnému veřejnému zájmu v říjnu 2018 poté, co o tom tweetoval matematik a počítačový vědec Robin Houston.[4] Dne 25. října 2018 zveřejnili Robin Houston, Jay Pantone a Vince Vatter vylepšenou verzi tohoto důkazu v On-line encyklopedie celočíselných sekvencí (OEIS).[5][6] Konkrétně pro „The Haruhi Problem“ (případ 14 symbolů) je dolní hranice aktuálně nejméně 93 884 313 611 a horní hranice je maximálně 93 924 230 411.[4]

Horní hranice

Dne 20. října 2018 úpravou konstrukce Aarona Williamse pro stavbu Hamiltonovské cesty skrz Cayleyův graf z symetrická skupina,[7] Greg Egan vymyslel algoritmus pro výrobu superpermutací délky n! + (n−1)! + (n−2)! + (n−3)! + n − 3.[2] Do roku 2018 to byly nejmenší známé superpermutace n ≥ 7. Dne 1. února 2019 však Bogdan Coanda oznámil, že našel superpermutaci pro n = 7 o délce 5907, nebo (n! + (n−1)! + (n−2)! + (n−3)! + n - 3) - 1, což byl nový rekord.[2] Dne 27. února 2019 vytvořil Egan pomocí myšlenek vyvinutých Robinem Houstonem superpermutaci pro n = 7 o délce 5906.[2] Zda existují podobné kratší superpermutace také pro hodnoty n > 7 zůstává otevřenou otázkou. Aktuální nejlepší dolní mez (viz část výše) pro n = 7 je stále 5884.

Viz také

Další čtení

  • Ashlock, Daniel A .; Tillotson, Jenett (1993), „Konstrukce malých superpermutací a minimálních injekčních superstrun“, Congressus Numerantium, 93: 91–98, Zbl  0801.05004
  • Plakát Anonymous 4chan; Houston, Robin; Pantone, Jay; Vatter, Vince (25. října 2018). „Dolní mez na délce nejkratšího supervzorku“ (PDF). On-line encyklopedie celočíselných sekvencí.

Reference

  1. ^ Johnston, Nathaniel (28. července 2013). „Nejedinečnost minimálních superpermutací“. Diskrétní matematika. 313 (14): 1553–1557. arXiv:1303.4150. Bibcode:2013arXiv1303.4150J. doi:10.1016 / j.disc.2013.03.024. Zbl  1368.05004. Citováno 16. března 2014.
  2. ^ A b C d E F Egan, Greg (20. října 2018). „Superpermutace“. gregegan.net. Citováno 15. ledna 2020.
  3. ^ Houston, Robin (21. srpna 2014), „Řešení problému minimální superpermutace“, arXiv:1408.5108 [math.CO ]
  4. ^ A b C Griggs, Mary Beth. „Anonymní příspěvek ve formátu 4chan by mohl pomoci vyřešit 25letou matematickou záhadu“. The Verge.
  5. ^ A b Klarreich, Erica (5. listopadu 2018). „Spisovatel sci-fi Greg Egan a Anonymous Math Whiz Advance Permutation Problem“. Časopis Quanta. Citováno 21. června 2020.
  6. ^ Anonymní plakát 4chan; Houston, Robin; Pantone, Jay; Vatter, Vince (25. října 2018). „Dolní mez na délce nejkratšího supervzorku“ (PDF). OEIS. Citováno 27. října 2018.
  7. ^ Aaron, Williams. "Hamiltonicita Cayleyho digrafu na symetrické skupině generovaná σ = (1 2 ... n) a τ = (1 2)". arXiv:1307,2549v3.

externí odkazy