Zobrazení zdroje stránky Superpermutace

[[File:Superpermutation distribution.png|thumb|Distribuce permutací v superpermutaci tří prvků]]
'''Superpermutace''' jsou pojmem [[kombinatorika|kombinatoriky]], kde superpermutace <math>n</math> symbolů je [[textový řetězec|řetězcem]] obsahujícím každou [[permutace|permutaci]] těchto <math>n</math> symbolů ve formě [[podřetězec|podřetězce]]. [[Triviální|Triviálně]] může být superpermutace složena prostým spojením všech řetězců jednotlivých permutací. Krom triviálního případu <math>n=1</math> lze najít řetězec kratší, poněvadž se tyto podřetězce mohou překrývat. Příkladně&nbsp;– pro <math>n = 2</math> existuje superpermutace <math>1221</math>, která obsahuje obě permutace, tj. <math>12</math> a <math>21</math>. Existuje ovšem i&nbsp;kratší řetězec <math>121</math>, jenž  je obsahuje také.

Bylo dokázáno, že nejkratší superpermutace <math>n</math> symbolů pro <math>1 \leq n \leq 5</math> má délku <math>1! + 2! + \dots + n!</math> <ref>{{OEIS|A180632}}</ref> Pro 1–4&nbsp;znaky mají superpermutace délky 1, 3, 9 a 33. Samotné superpermutace poté mají podobu <math>1</math>, <math>121</math>, <math>123121321</math> a <math>12341231</math><math>42312431</math><math>21342132</math><math>413214321</math>. Pro <math>n = 5</math> existuje několik známých superpermutací o&nbsp;délce 153 znaků, jedna taková je ukázána níže. Odlišná superpermutace by šla vytvořit prohozením všech čtyřek a&nbsp;pětek v druhé polovině (po tučně označeném písmenu '''2'''):<ref>{{cite journal |first=Nathaniel |last=Johnston |date=July 28, 2013 |arxiv=1303.4150 |title=Non-uniqueness of minimal superpermutations |journal=Discrete Mathematics |volume=313 |issue=14 |pages=1553–1557 |doi=10.1016/j.disc.2013.03.024 |bibcode=2013arXiv1303.4150J |url=http://www.njohnston.ca/publications/non-uniqueness-of-minimal-superpermutations/ |accessdate=March 16, 2014 | zbl=1368.05004|s2cid=12018639 | jazyk=en }}</ref>

<math>12345123</math><math>41523412</math><math>53412354</math><math>12314523</math><math>14253142</math><math>35142315</math><math>42312453</math><math>12435124</math><math>31524312</math><math>5431 \mathbf{2} 134</math><math>52134251</math><math>34215342</math><math>13542132</math><math>45132415</math><math>32413524</math><math>13254132</math><math>14532143</math><math>52143251</math><math>432154321</math>.

Pro <math>n > 5</math> zatím nebyl nalezen jednoznačný vztah, pomocí kterého by šlo superpermutaci přímo hledat, jsme ovšem schopni spočíst spodní a&nbsp;horní mez intervalu, ve kterém se délka superpermutace nachází.

== Hledání superpermutací ==
[[file:superpermutations.jpg|thumb|Diagram vytváření superpermutace 3&nbsp;symbolů ze superpermutace 2&nbsp;symbolů]]
Jeden z&nbsp;nejběžnějších algoritmů hledání superpermutace řádu <math>n</math> je algoritmus rekurzivní. V prvním kroku rozdělíme superpermutaci <math>n-1</math> prvků do svých permutací seřazených podle toho, v&nbsp;jakém pořadí se vyskytují v superpermutaci. Každá z&nbsp;těchto permutací je následně umístěna vedle kopie sebe samé, přičemž mezi obě kopie je přidán symbol <math>n</math>. Nakonec jsou všechny vzniklé struktury umístěny vedle sebe a všechny sousední identické symboly jsou sloučeny.<ref name="Greg Egan">{{cite web|url=http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html|title=Superpermutations|last=Egan|first=Greg|date=20 October 2018|website=gregegan.net|access-date=15 January 2020}}</ref>

Například superpermutace třetího řádu může být vytvořena z&nbsp;jiné se dvěma symboly. Začneme se superpermutací <math>121</math> a&nbsp;rozdělíme ji na permutace <math>12</math> a <math>21</math>. Vytvoříme kopie a&nbsp;přidáme další symbol, čímž vzniknou řetězce <math>12312</math> a <math>21321</math>. Ty spojíme, čímž následně vznikne <math>1231221321</math>. Redundantní opakované dvojky uprostřed se můžeme zbavit, čímž vznikne kratší řetězec <math>123121321</math>, jenž je optimální superpermutací řádu 3. Tímto algoritmem jsme schopni vytvořit optimální superpermutace pro každé <math>n \leq 5</math>, pro vyšší <math>n</math> algoritmus není platný a jím vytvořené superpermutace mají od těch optimálních daleko.<ref name="Greg Egan"/>

Superpermutace můžeme hledat i&nbsp;přes vytvoření [[Graf (teorie grafů)|grafu]], kde každá permutace je [[Vrchol (graf)|vrcholem]] spojeným hranou. Každá hrana má [[Graf (teorie grafů)#Ohodnocení grafu|váhu]], váha je zde určována dle počtu znaků, které můžeme přidat na konec permutace (vypustit stejný počet znaků z počátku), abychom získali další permutaci<ref name="Greg Egan"/>. Ku příkladu, hrana mezi permutacemi <math>123</math> a <math>312</math> má váhu&nbsp;2, protože <math>123 + 12 = 12312 = 312</math>. Každá [[Hamiltonovský graf#Hamiltonovská kružnice|hamiltonovská kružnice]] vedená tímto grafem je superpermutací, problém hledání cesty s&nbsp;nejmenší vahou zde nabývá formy [[Problém obchodního cestujícího|problému obchodního cestujícího]]. První nalezená superpermutace s&nbsp;délkou kratší než <math>1! + 2! + \ldots + n!</math> byla získána právě přes počítačové vyhledávání informatikem Robinem Houstonem.<ref>{{Citace elektronické monografie
| příjmení = Houston
| jméno = Robin
| titul = Tackling the Minimal Superpermutation Problem
| url = https://www.researchgate.net/publication/264979617_Tackling_the_Minimal_Superpermutation_Problem
| datum vydání = 2014-08-01
| stránky = 5
| datum přístupu = 2025-02-18
| jazyk = en
}}</ref>
=== Dolní meze, téže problém Haruhi ===
Dne 27.&nbsp;září 2011 neznámý přispěvatel na nástěnku „Science & Math“ ''(Věda a matematika)'' [[Imageboard|Imageboard fóra]] [[4chan]] zveřejnil důkaz o&nbsp;délce nejkratší superpermutace <math>n</math> symbolů pro <math>n \geq 2</math>. Ta má délku alespoň <math>n! + (n-1)! + (n-2)! + n - 3</math>. Občas je nazýván dle japonského animovaného seriálu [[Suzumija Haruhi no júucu|Haruhi]]{{Poznámka
|Animovaný seriál ''Suzumija Haruhi no júucu'' (v doslovném překladu ''Melancholie Haruhi Suzumijové'') ve&nbsp;svém příběhu obsahuje časovou smyčku, tato část zabírá 8 z&nbsp;původních 14&nbsp;episod. Těchto 8 episod je, až na malé detaily, téměř totožné. Tvůrci z uměleckého záměru a&nbsp;ze snahy vyhnout se nepříjemnému diváckému zážitku, v&nbsp;němž se budou episody většinu času takřka opakovat, animovaný seriál původně vydávali v&nbsp;jiném než chronologickém pořadí. V pozdějších vydáních (na nosiče DVD atp.) však již episody byly seřazeny chronologicky, a tedy&nbsp;nikoliv dle linie vypravěče (tzv. ''Kyon order'', Kjónovo pořadí). Preferované pořadí, či snad některá vysněná fanouškovská, která se lišila od obou oficiálních, se stala tématem debat mezi příznivci seriálu.<ref>{{Citace elektronické monografie
| příjmení = Bannerjee
| jméno = Ritam
| titul = The Melancholy Of Haruhi Suzumiya Watch Order Explained!
| url = https://animehunch.com/haruhi-suzumiya-watch-order/
| datum aktualizace = 2022-04-09
| datum přístupu = 2025-02-21
| jazyk = en 
}}</ref> 
<ref>{{Citace elektronické monografie
| příjmení = Bennet
| jméno = Tyler
| titul = The Melancholy of Haruhi Suzumiya Watch Order in 2024, Explained
| url = https://letsweaboo.com/news/the-melancholy-of-haruhi-suzumiya-watch-order-in-2024-explained_a147
| datum vydání = 2022-03-10
| datum přístupu = 2025-02-21
| jazyk = en 
}}</ref>
}}, který používá techniku [[nelineární vypravování|nelineárního vypravování]]&nbsp;– uživatelé tohoto fóra si položili otázku, kolik nejméně episod by museli zhlédnout, aby viděli všech 14 episod v každém možném pořadí.<ref>{{Cite web |last=Anon |first=- San |date=September 17, 2011 |title=Permutations Thread III ニア愛 |url=https://warosu.org/sci/thread/S3751105#p3751197 |website=Warosu}}</ref><ref name=":1">{{Cite web|last=Klarreich|first=Erica|date=November 5, 2018|title=Sci-Fi Writer Greg Egan and Anonymous Math Whiz Advance Permutation Problem|url=https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-whiz-advance-permutation-problem-20181105/|archive-url=|archive-date=|access-date=2025-02-18|website=[[Quanta Magazine]]|language=en}}</ref> Do hledáčku veřejnosti se důkaz dostal v roce 2018 poté, co Robin Houston o důkazu napsal příspěvek na síť [[X (sociální síť)|Twitter]].<ref>{{Citace elektronické monografie
|příjmení1=Griggs 
|jméno1=Mary Beth 
|titul=An anonymous 4chan post could help solve a 25-year-old math mystery 
|url=https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery 
|web=The Verge}}</ref> Dne 25. října 2018 Robin Houston, Jay Pantone a Vince Vatter publikovali formalizovanou verzi důkazu na [[On-Line Encyclopedia of Integer Sequences|Online encyklopedii celočíselných sekvencí]].<ref name=":1" /><ref>{{cite web 
|author1=((Anonymous 4chan poster)) 
|last2=Houston 
|first2=Robin 
|last3=Pantone 
|first3=Jay 
|last4=Vatter 
|first4=Vince 
|date=October 25, 2018 
|title=A lower bound on the length of the shortest superpattern 
|url=https://oeis.org/A180632/a180632.pdf 
|accessdate=27 October 2018 
|website=OEIS 
| language = en}}</ref> 
Zveřejněná forma tohoto článku, připisována „Anonymnímu přispěvateli fóra 4chan“ se objevila v [[American Mathematical Monthly]].<ref name="engenvatter">{{citace elektronické monografie
| příjmení1 = Engen | jméno1 = Michael 
| příjmení2 = Vatter | jméno2 = Vincent
| titul = Containing all permutations
| doi = 10.1080/00029890.2021.1835384
| doi-access = free
| journal = [[American Mathematical Monthly]]
| rok = 2021
| svazek = 128
| vydání = 1
| strany = 4–24
| arxiv = 1810.08252
}}</ref>

Specificky pro „problém Haruhi“ (14&nbsp;episod, tj. 14&nbsp;symbolů) jsou aktuálně nejlepší známé spodní, respektive horní meze 93 884 313 611, resp. 93 924 230 411. Při průměrné délce episody to znamená, že zhlédnout všechny episody ve všech možných pořadích by trvalo zhruba 4,3&nbsp;milionu let.<ref>{{Cite web |last=Spalding |first=Katie |date=2018-10-30 |title=4chan Just Solved A Decades-Old Mathematical Mystery |url=https://www.iflscience.com/an-anonymous-online-anime-fan-just-solved-a-problem-thats-been-eluding-mathematicians-for-decades-50364 |access-date=2023-10-05 |website=IFLScience |language=en}}</ref>

=== Horní meze ===
Dne 20.&nbsp;října 2018 sestrojil autor science fiction a matematik [[Greg Egan]] algoritmus pro hledání superpermutačních řetězců délky <math>n! + (n-1)! + (n-2)! + (n-3)! + n - 3</math>.<ref name ="Greg Egan"/> přizpůsobením konstrukce Aarona Williamse<ref>{{Citace arXiv
|id=1307.2549v3
|jméno=Williams
|příjmení=Aaron <!--
|titul=Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2) -->
|rok=2013
|třída = Math.C0
}}</ref> pro vytváření [[Hamiltonovský graf#Hamiltonovská kružnice|hamiltonovských kružnic]] skrze [[Cayleyův graf]] [[symetrická grupa|symetrické grupy]]. V&nbsp;té době šlo o nejkratší známé superpermutační řetězce pro <math> n \geq 7</math>. Dne 1.&nbsp;února 2019 Bogdan Coanda oznámil, že pro <math>n=7</math> našel superpermutační řetězec délky 5907, což je ekvivalentní s <math>(n! + (n-1)! + (n-2)! + (n-3)! + n - 3) - 1</math>, šlo tedy o&nbsp;nový rekord. Dne 27. února 2019, využívaje myšlenky vyvinuté Robinem Houstonem, Egan pro <math>n = 7</math> nalezl superpermutační řetězec o délce 5906. Zda existují podobné kratší superpermutační řetězce pro hodnoty <math>n>7</math>, zůstává nevyřešenou otázkou. Aktuální nejlepší známou dolní mezí (vizte výše uvedenou sekci) pro <math>n = 7</math> je stále 5884.

== Odkazy ==
=== Poznámky ===
{{Poznámky}}
=== Reference ===
{{Překlad|jazyk=en |článek=Superpermutation |revize=1274263574 }} <references />

===Literatura===
*{{Citation |first1=Daniel A. |last1=Ashlock |first2=Jenett |last2=Tillotson |year=1993 |title=Construction of small superpermutations and minimal injective superstrings |journal=Congressus Numerantium |volume=93  | pages=91–98 | zbl=0801.05004 }}
*{{Cite journal |last1=((Anonymous 4chan Poster)) |last2=Houston |first2=Robin |last3=Pantone |first3=Jay |last4=Vatter |first4=Vince |date=October 25, 2018 |title=A lower bound on the length of the shortest superpattern |url=https://oeis.org/A180632/a180632.pdf |journal=[[On-Line Encyclopedia of Integer Sequences]]}}

=== Související články ===
<!--*[[Superpattern]], a permutation that contains each permutation of ''n'' symbols as a [[permutation pattern]]
-->
*[[De Bruijnova posloupnost]], podobný problém s cyklickými řadami

===Externí odkazy===
* [http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/ The Minimal Superpermutation Problem – Nathaniel Johnston's blog]
* {{cite web|last1=Grime|first1=James|title=Superpermutations - Numberphile|url=https://www.youtube.com/watch?v=wJGE4aEWc28|website=YouTube|publisher=[[Brady Haran]]|accessdate=1 February 2018|format=video}}
* [https://warosu.org/sci/thread/S3751105#p3751197 The original 4chan post on /sci/], archivováno na warosu.org
* [https://twitter.com/robinhouston/status/1054637891085918209 Tweet] Robina Houstona, který zviditelnil příspěvek na diskusním fóru 4chan 
* [https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-whiz-advance-permutation-problem-20181105/ Článek] o hledání krátkých superpermutacích v [[Magazín Quanta|magazínu Quanta]]
* [https://www.karlin.mff.cuni.cz/~holub/slova.htm Štěpán Holub – Kombinatorika na slovech]
* {{Citace elektronické monografie | příjmení = Bannerjee | jméno = Ritam | titul = The Melancholy Of Haruhi Suzumiya Watch Order Explained! | url = https://animehunch.com/haruhi-suzumiya-watch-order/ | datum aktualizace = 2022-04-09 | datum přístupu = 2025-02-21 | jazyk = en 
}}

[[Kategorie:Kombinatorika na slovech]]
[[Kategorie:Permutace]]