www.wikidata.uk-ua.nina.az

Суперпермутація У комбінаториці суперпермутація n символів рядок що містить кожну можливу перестановку n символів як під

Суперпермутація

У комбінаториці, суперпермутація n символів — рядок, що містить кожну можливу перестановку n символів, як підрядок. Тривіальні суперпермутації можливо створити, просто записавши всі перестановки підряд, проте вони можуть бути й коротшими (за винятком найпростішого випадку, при n = 1), бо накладання підрядків дозволене. Наприклад, при n = 2, суперпермутація 1221 містить у собі всі перестановки (12, 21), але й коротший рядок 121 також містить ті ж самі перестановки.

Розподіл пермутацій у суперпермутації 3 символів

Доведено, що при 1 ≤ n ≤ 5, найменша суперпермутація n символів має довжину 1! + 2! + … + n! (послідовність A180632 з Онлайн енциклопедії послідовностей цілих чисел, OEIS). Довжини перших чотирьох найменших суперпермутацій: 1, 3, 9 та 33, що мають наступний вигляд: 1, 121, 123121321 та 123412314231243121342132413214321 відповідно. Однак для n = 5 є кілька різних найменших суперпермутацій, що всі мають довжину 153. Нижче наведена одна з цих суперпермутацій. Іншу суперпермутацію такої ж довжини можна отримати, якщо у другій половині рядка (після 2, що виділена жирним) поміняти місцями всі 4 та 5:

12345123­41523412­53412354­12314523­14253142­35142315­42312453­12435124­31524312­54312134­52134251­34215342­13542132­45132415­32413524­13254132­14532143­52143251­432154321

Для рядків, де n > 5, найменші суперпермутації ще не знайдені, та досі не відомий спосіб їх пошуку, однак вже розраховані їхні нижні та верхні межі.

Знаходження суперпермутацій ред.

Діаграма створення суперпермутації 3 символів з суперпермутації 2 символів

Один із найпоширеніших алгоритмів утворення суперпермутації порядку  — рекурсивний алгоритм. Спочатку, суперпермутація порядку ділиться на свої окремі перестановки у тому порядку, в якому вони з'явились у самій суперпермутації. Потім кожна з цих пермутацій розташовується після самої себе, та між ними двома додається n-ий символ. Зрештою, кожний з утворених таким чином рядків розташовується один після одного, та всі ідентичні символи об'єднуються.

Наприклад, суперпермутацію 3 порядку можна створити з суперпермутації 2 порядку. На початку є суперпермутація 121, що розділяється на перестановки 12 та 21; ці перестановки дублюються та записуються, як 12312 та 21321. Потім вони об'єднуються разом, внаслідок чого утворюється рядок 1231221321. Дві двійки посередині об'єднуються, та в результаті виходить рядок 123121321, що справді є суперпермутацією 3 порядку. Цей алгоритм дає найкоротшу суперпермутацію для всіх n, що менше або дорівнюють 5, проте далі стають все більше та є довшими за коротші можливі суперпермутації.

Інший спосіб знайти суперпермутацію — побудувати граф, де кожна перестановка є вершиною, та всі вони між собою з'єднані ребрами. Кожному ребру призначається вага, де значення ваги — кількість символів, яку треба додати до кінця однієї перестановки (прибравши таку ж кількість символів з початку перестановки), аби отримати іншу перестановку. Наприклад, ребро між вершинами 123 та 312 має вагу 2, тому що 123 + 12 = 12312 = 312. Будь-який Гамільтонів шлях, отриманий у цьому графі є суперпермутацією, а проблема пошуку шляху з найменшою вагою аналогічна задачі комівояжера. Перший приклад суперпермутації, меншої за було знайдено Робіном Х'юстоном, шляхом комп'ютерного розрахунку цим методом.

Нижні межі, або «Проблема Харухі» ред.

У вересні 2011 року, анонімний користувач дошки «Наука і математика» (/sci/) на сайті 4chan довів, що найменша можлива суперпермутація n символів (за n ≥ 2) має довжину, що складає n! + (n−1)! + (n−2)! + n − 3. Оригінальний дописувач опублікував питання під назвою «Проблема Харухі», посилаючись на аніме-серіал Меланхолія Судзумії Харухі: «Якби ви хотіли побачити 14 серій першого сезону серіалу в кожному можливому порядку, то яку найменшу можливу кількість серій вам би довелось подивитись?». Це доведення нижньої межі стало відомим у жовтні 2018 року, коли математик та комп'ютерний вчений Робін Х'юстон написав про це у Твіттері. 25 жовтня 2018 року, Робін Х'юстон, Джей Пентон, та Вінс Веттер опублікували коректно оформлену версію цього доведення у Інтерактивній енциклопедії цілочислових послідовностей. Видане доведення, приписуване «Анонімному дописувачу 4chan», згадується у роботі Engen and Vatter (2021).

Для випадку «Проблеми Харухі» (суперпермутація при n = 14), нині відомі нижня та верхня межа — 93 884 313 611 та 93 924 230 411 відповідно. Тобто, аби побачити 14 серій у всіх можливих послідовностях, знадобиться щонайменше 4,3 мільйона років.

Верхні межі ред.

20 жовтня 2018, науковий фантаст та математик Грег Іген адаптував розробку Аарона Вільямса по побудові Гамільтонових шляхів по графу Келі симетричної групи та розробив алгоритм, що дозволяє знаходити суперпермутації довжини n! + (n−1)! + (n−2)! + (n−3)! + n − 3. До 2018 року це були найменші відомі суперпермутації для значень n ≥ 7. Однак 1 лютого 2019 року, Богдан Коанда заявив, що знайшов суперпермутацію для n = 7 з довжиною 5907, або (n! + (n−1)! + (n−2)! + (n−3)! + n − 3) − 1, що стало новим рекордом. 27 лютого 2019 року, на базі ідей Робіна Х'юстона, Іган знайшов суперпермутацію для n = 7 з довжиною 5906. Чи існують ще коротші суперпермутації для значень n > 7 — невідомо. Поки що, доведена нижня можлива межа довжини (див. попередній розділ) для n = 7 дорівнює 5884.

Див. також ред.

Література ред.

  • Ashlock, Daniel A.; Tillotson, Jenett (1993). Construction of small superpermutations and minimal injective superstrings. Congressus Numerantium. 93: 91–98. Zbl 0801.05004. 
  • Anonymous 4chan Poster; Houston, Robin; Pantone, Jay; Vatter, Vince (25 жовтня 2018). A lower bound on the length of the shortest superpattern. Інтерактивна енциклопедія цілочислових послідовностей. 

Примітки ред.

  1. Johnston, Nathaniel (28 липня 2013). Non-uniqueness of minimal superpermutations. Discrete Mathematics. 313 (14): 1553–1557. arXiv:1303.4150. Bibcode:2013arXiv1303.4150J. doi:10.1016/j.disc.2013.03.024. S2CID 12018639. Zbl 1368.05004. Процитовано 16 березня 2014. 
  2. ↑ Egan, Greg (20 October 2018). Superpermutations. gregegan.net. Процитовано 15 January 2020. 
  3. ↑ Griggs, Mary Beth. An anonymous 4chan post could help solve a 25-year-old math mystery. The Verge. 
  4. Anon, - San (17 вересня 2011). Permutations Thread III ニア愛. Warosu. 
  5. ↑ Klarreich, Erica (5 листопада 2018). Sci-Fi Writer Greg Egan and Anonymous Math Whiz Advance Permutation Problem. Quanta Magazine (англ.). Процитовано 21 червня 2020. 
  6. Anonymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince (25 жовтня 2018). A lower bound on the length of the shortest superpattern. OEIS. Процитовано 27 October 2018. 
  7. Engen, Michael; Vatter, Vincent (2021). Containing all permutations. American Mathematical Monthly. 128 (1): 4–24. arXiv:1810.08252. doi:10.1080/00029890.2021.1835384. 
  8. Spalding, Katie (30 жовтня 2018). 4chan Just Solved A Decades-Old Mathematical Mystery. IFLScience (англ.). Процитовано 5 жовтня 2023. 
  9. Aaron, Williams (2013). «Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2)». arXiv:1307.2549v3 [math.CO]. 

Посилання ред.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
U kombinatorici superpermutaciya n simvoliv ryadok sho mistit kozhnu mozhlivu perestanovku n simvoliv yak pidryadok Trivialni superpermutaciyi mozhlivo stvoriti prosto zapisavshi vsi perestanovki pidryad prote voni mozhut buti j korotshimi za vinyatkom najprostishogo vipadku pri n 1 bo nakladannya pidryadkiv dozvolene Napriklad pri n 2 superpermutaciya 1221 mistit u sobi vsi perestanovki 12 21 ale j korotshij ryadok 121 takozh mistit ti zh sami perestanovki Rozpodil permutacij u superpermutaciyi 3 simvolivDovedeno sho pri 1 n 5 najmensha superpermutaciya n simvoliv maye dovzhinu 1 2 n poslidovnist A180632 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Dovzhini pershih chotiroh najmenshih superpermutacij 1 3 9 ta 33 sho mayut nastupnij viglyad 1 121 123121321 ta 123412314231243121342132413214321 vidpovidno Odnak dlya n 5 ye kilka riznih najmenshih superpermutacij sho vsi mayut dovzhinu 153 Nizhche navedena odna z cih superpermutacij Inshu superpermutaciyu takoyi zh dovzhini mozhna otrimati yaksho u drugij polovini ryadka pislya 2 sho vidilena zhirnim pominyati miscyami vsi 4 ta 5 1 12345123 41523412 53412354 12314523 14253142 35142315 42312453 12435124 31524312 54312134 52134251 34215342 13542132 45132415 32413524 13254132 14532143 52143251 432154321Dlya ryadkiv de n gt 5 najmenshi superpermutaciyi she ne znajdeni ta dosi ne vidomij sposib yih poshuku odnak vzhe rozrahovani yihni nizhni ta verhni mezhi Zmist 1 Znahodzhennya superpermutacij 1 1 Nizhni mezhi abo Problema Haruhi 1 2 Verhni mezhi 2 Div takozh 3 Literatura 4 Primitki 5 PosilannyaZnahodzhennya superpermutacij red nbsp Diagrama stvorennya superpermutaciyi 3 simvoliv z superpermutaciyi 2 simvolivOdin iz najposhirenishih algoritmiv utvorennya superpermutaciyi poryadku n displaystyle n nbsp rekursivnij algoritm Spochatku superpermutaciya poryadku n 1 displaystyle n 1 nbsp dilitsya na svoyi okremi perestanovki u tomu poryadku v yakomu voni z yavilis u samij superpermutaciyi Potim kozhna z cih permutacij roztashovuyetsya pislya samoyi sebe ta mizh nimi dvoma dodayetsya n ij simvol Zreshtoyu kozhnij z utvorenih takim chinom ryadkiv roztashovuyetsya odin pislya odnogo ta vsi identichni simvoli ob yednuyutsya 2 Napriklad superpermutaciyu 3 poryadku mozhna stvoriti z superpermutaciyi 2 poryadku Na pochatku ye superpermutaciya 121 sho rozdilyayetsya na perestanovki 12 ta 21 ci perestanovki dublyuyutsya ta zapisuyutsya yak 12312 ta 21321 Potim voni ob yednuyutsya razom vnaslidok chogo utvoryuyetsya ryadok 1231221321 Dvi dvijki poseredini ob yednuyutsya ta v rezultati vihodit ryadok 123121321 sho spravdi ye superpermutaciyeyu 3 poryadku Cej algoritm daye najkorotshu superpermutaciyu dlya vsih n sho menshe abo dorivnyuyut 5 prote dali stayut vse bilshe ta ye dovshimi za korotshi mozhlivi superpermutaciyi 2 Inshij sposib znajti superpermutaciyu pobuduvati graf de kozhna perestanovka ye vershinoyu ta vsi voni mizh soboyu z yednani rebrami Kozhnomu rebru priznachayetsya vaga de znachennya vagi kilkist simvoliv yaku treba dodati do kincya odniyeyi perestanovki pribravshi taku zh kilkist simvoliv z pochatku perestanovki abi otrimati inshu perestanovku 2 Napriklad rebro mizh vershinami 123 ta 312 maye vagu 2 tomu sho 123 12 12312 312 Bud yakij Gamiltoniv shlyah otrimanij u comu grafi ye superpermutaciyeyu a problema poshuku shlyahu z najmenshoyu vagoyu analogichna zadachi komivoyazhera Pershij priklad superpermutaciyi menshoyi za 1 2 n displaystyle 1 2 ldots n nbsp bulo znajdeno Robinom H yustonom shlyahom komp yuternogo rozrahunku cim metodom Nizhni mezhi abo Problema Haruhi red U veresni 2011 roku anonimnij koristuvach doshki Nauka i matematika sci na sajti 4chan doviv sho najmensha mozhliva superpermutaciya n simvoliv za n 2 maye dovzhinu sho skladaye n n 1 n 2 n 3 3 Originalnij dopisuvach opublikuvav pitannya pid nazvoyu Problema Haruhi posilayuchis na anime serial Melanholiya Sudzumiyi Haruhi 4 Yakbi vi hotili pobachiti 14 serij pershogo sezonu serialu v kozhnomu mozhlivomu poryadku to yaku najmenshu mozhlivu kilkist serij vam bi dovelos podivitis 5 Ce dovedennya nizhnoyi mezhi stalo vidomim u zhovtni 2018 roku koli matematik ta komp yuternij vchenij Robin H yuston napisav pro ce u Tvitteri 3 25 zhovtnya 2018 roku Robin H yuston Dzhej Penton ta Vins Vetter opublikuvali korektno oformlenu versiyu cogo dovedennya u Interaktivnij enciklopediyi cilochislovih poslidovnostej 5 6 Vidane dovedennya pripisuvane Anonimnomu dopisuvachu 4chan zgaduyetsya u roboti Engen and Vatter 2021 7 Dlya vipadku Problemi Haruhi superpermutaciya pri n 14 nini vidomi nizhnya ta verhnya mezha 93 884 313 611 ta 93 924 230 411 vidpovidno 3 Tobto abi pobachiti 14 serij u vsih mozhlivih poslidovnostyah znadobitsya shonajmenshe 4 3 miljona rokiv 8 Verhni mezhi red 20 zhovtnya 2018 naukovij fantast ta matematik Greg Igen adaptuvav rozrobku Aarona Vilyamsa po pobudovi Gamiltonovih shlyahiv po grafu Keli simetrichnoyi grupi 9 ta rozrobiv algoritm sho dozvolyaye znahoditi superpermutaciyi dovzhini n n 1 n 2 n 3 n 3 2 Do 2018 roku ce buli najmenshi vidomi superpermutaciyi dlya znachen n 7 Odnak 1 lyutogo 2019 roku Bogdan Koanda zayaviv sho znajshov superpermutaciyu dlya n 7 z dovzhinoyu 5907 abo n n 1 n 2 n 3 n 3 1 sho stalo novim rekordom 2 27 lyutogo 2019 roku na bazi idej Robina H yustona Igan znajshov superpermutaciyu dlya n 7 z dovzhinoyu 5906 2 Chi isnuyut she korotshi superpermutaciyi dlya znachen n gt 7 nevidomo Poki sho dovedena nizhnya mozhliva mezha dovzhini div poperednij rozdil dlya n 7 dorivnyuye 5884 Div takozh red Poslidovnist de Brejna podibna problema ale z ciklichnimi poslidovnostyamiLiteratura red Ashlock Daniel A Tillotson Jenett 1993 Construction of small superpermutations and minimal injective superstrings Congressus Numerantium 93 91 98 Zbl 0801 05004 Anonymous 4chan Poster Houston Robin Pantone Jay Vatter Vince 25 zhovtnya 2018 A lower bound on the length of the shortest superpattern Interaktivna enciklopediya cilochislovih poslidovnostej Primitki red Johnston Nathaniel 28 lipnya 2013 Non uniqueness of minimal superpermutations Discrete Mathematics 313 14 1553 1557 arXiv 1303 4150 Bibcode 2013arXiv1303 4150J doi 10 1016 j disc 2013 03 024 S2CID 12018639 Zbl 1368 05004 Procitovano 16 bereznya 2014 a b v g d e Egan Greg 20 October 2018 Superpermutations gregegan net Procitovano 15 January 2020 a b v Griggs Mary Beth An anonymous 4chan post could help solve a 25 year old math mystery The Verge Anon San 17 veresnya 2011 Permutations Thread III ニア愛 Warosu a b Klarreich Erica 5 listopada 2018 Sci Fi Writer Greg Egan and Anonymous Math Whiz Advance Permutation Problem Quanta Magazine angl Procitovano 21 chervnya 2020 Anonymous 4chan poster Houston Robin Pantone Jay Vatter Vince 25 zhovtnya 2018 A lower bound on the length of the shortest superpattern OEIS Procitovano 27 October 2018 Engen Michael Vatter Vincent 2021 Containing all permutations American Mathematical Monthly 128 1 4 24 arXiv 1810 08252 doi 10 1080 00029890 2021 1835384 Spalding Katie 30 zhovtnya 2018 4chan Just Solved A Decades Old Mathematical Mystery IFLScience angl Procitovano 5 zhovtnya 2023 Aaron Williams 2013 Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by s 1 2 n and t 1 2 arXiv 1307 2549v3 math CO Posilannya red The Minimal Superpermutation Problem Nathaniel Johnston s blog Grime James Superpermutations Numberphile video YouTube Bredi Haran Procitovano 1 February 2018 Originalni dopisi na 4chan na doshci sci arhivovani u warosu org Tvit Robina H yustona sho zvernuv uvagu na posti u 4chan Stattya pro problemu znahodzhennya korotkih superpermutacij u zhurnali Quanta Otrimano z https uk wikipedia org w index php title Superpermutaciya amp oldid 42132650