Суперпермутація
У комбінаториці, суперпермутація n символів — рядок, що містить кожну можливу перестановку n символів, як підрядок. Тривіальні суперпермутації можливо створити, просто записавши всі перестановки підряд, проте вони можуть бути й коротшими (за винятком найпростішого випадку, при n = 1), бо накладання підрядків дозволене. Наприклад, при n = 2, суперпермутація 1221 містить у собі всі перестановки (12, 21), але й коротший рядок 121 також містить ті ж самі перестановки.
Доведено, що при 1 ≤ n ≤ 5, найменша суперпермутація n символів має довжину 1! + 2! + … + n![1]. Довжини перших чотирьох найменших суперпермутацій: 1, 3, 9 та 33, що мають наступний вигляд: 1, 121, 123121321 та 123412314231243121342132413214321 відповідно. Однак для n = 5 є кілька різних найменших суперпермутацій, що всі мають довжину 153. Нижче наведена одна з цих суперпермутацій. Іншу суперпермутацію такої ж довжини можна отримати, якщо у другій половині рядка (після 2, що виділена жирним) поміняти місцями всі 4 та 5[2]:
123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321
Для рядків, де n > 5, найменші суперпермутації ще не знайдені, та досі не відомий спосіб їх пошуку, однак вже розраховані їхні нижні та верхні межі.
Один із найпоширеніших алгоритмів утворення суперпермутації порядку — рекурсивний алгоритм. Спочатку, суперпермутація порядку ділиться на свої окремі перестановки у тому порядку, в якому вони з'явились у самій суперпермутації. Потім кожна з цих пермутацій розташовується після самої себе, та між ними двома додається n-ий символ. Зрештою, кожний з утворених таким чином рядків розташовується один після одного, та всі ідентичні символи об'єднуються[3].
Наприклад, суперпермутацію 3 порядку можна створити з суперпермутації 2 порядку. На початку є суперпермутація 121, що розділяється на перестановки 12 та 21; ці перестановки дублюються та записуються, як 12312 та 21321. Потім вони об'єднуються разом, внаслідок чого утворюється рядок 1231221321. Дві двійки посередині об'єднуються, та в результаті виходить рядок 123121321, що справді є суперпермутацією 3 порядку. Цей алгоритм дає найкоротшу суперпермутацію для всіх n, що менше або дорівнюють 5, проте далі стають все більше та є довшими за коротші можливі суперпермутації[3].
Інший спосіб знайти суперпермутацію — побудувати граф, де кожна перестановка є вершиною, та всі вони між собою з'єднані ребрами. Кожному ребру призначається вага, де значення ваги — кількість символів, яку треба додати до кінця однієї перестановки (прибравши таку ж кількість символів з початку перестановки), аби отримати іншу перестановку[3]. Наприклад, ребро між вершинами 123 та 312 має вагу 2, тому що 123 + 12 = 12312 = 312. Будь-який Гамільтонів шлях, отриманий у цьому графі є суперпермутацією, а проблема пошуку шляху з найменшою вагою аналогічна задачі комівояжера. Перший приклад суперпермутації, меншої за було знайдено Робіном Х'юстоном, шляхом комп'ютерного розрахунку цим методом.
У вересні 2011 року, анонімний користувач дошки «Наука і математика» (/sci/) на сайті 4chan довів, що найменша можлива суперпермутація n символів (за n ≥ 2) має довжину, що складає n! + (n−1)! + (n−2)! + n − 3[4]. Оригінальний дописувач опублікував питання під назвою «Проблема Харухі», посилаючись на аніме-серіал Меланхолія Судзумії Харухі[5]: «Якби ви хотіли побачити 14 серій першого сезону серіалу в кожному можливому порядку, то яку найменшу можливу кількість серій вам би довелось подивитись?»[6]. Це доведення нижньої межі стало відомим у жовтні 2018 року, коли математик та комп'ютерний вчений Робін Х'юстон написав про це у Твіттері[4]. 25 жовтня 2018 року, Робін Х'юстон, Джей Пентон, та Вінс Веттер опублікували коректно оформлену версію цього доведення у Інтерактивній енциклопедії цілочислових послідовностей[6][7]. Видане доведення, приписуване «Анонімному дописувачу 4chan», згадується у роботі Engen and Vatter (2021)[8].
Для випадку «Проблеми Харухі» (суперпермутація при n = 14), нині відомі нижня та верхня межа — 93 884 313 611 та 93 924 230 411 відповідно[4]. Тобто, аби побачити 14 серій у всіх можливих послідовностях, знадобиться щонайменше 4,3 мільйона років[9].
20 жовтня 2018, науковий фантаст та математик Грег Іген адаптував розробку Аарона Вільямса по побудові Гамільтонових шляхів по графу Келі симетричної групи[10] та розробив алгоритм, що дозволяє знаходити суперпермутації довжини n! + (n−1)! + (n−2)! + (n−3)! + n − 3[3]. До 2018 року це були найменші відомі суперпермутації для значень n ≥ 7. Однак 1 лютого 2019 року, Богдан Коанда заявив, що знайшов суперпермутацію для n = 7 з довжиною 5907, або (n! + (n−1)! + (n−2)! + (n−3)! + n − 3) − 1, що стало новим рекордом[3]. 27 лютого 2019 року, на базі ідей Робіна Х'юстона, Іган знайшов суперпермутацію для n = 7 з довжиною 5906[3]. Чи існують ще коротші суперпермутації для значень 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 (PDF). Інтерактивна енциклопедія цілочислових послідовностей.
- ↑ послідовність A180632 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
- ↑ 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.
- ↑ а б в г д е Egan, Greg (20 жовтня 2018). Superpermutations. gregegan.net. Процитовано 15 січня 2020.
- ↑ а б в Griggs, Mary Beth. An anonymous 4chan post could help solve a 25-year-old math mystery. The Verge.
- ↑ Anon, - San (17 вересня 2011). Permutations Thread III ニア愛. Warosu.
- ↑ а б Klarreich, Erica (5 листопада 2018). Sci-Fi Writer Greg Egan and Anonymous Math Whiz Advance Permutation Problem. Quanta Magazine (англ.). Процитовано 21 червня 2020.
- ↑ Anonymous 4chan poster; Houston, Robin; Pantone, Jay; Vatter, Vince (25 жовтня 2018). A lower bound on the length of the shortest superpattern (PDF). OEIS. Процитовано 27 жовтня 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 жовтня 2018). 4chan Just Solved A Decades-Old Mathematical Mystery. IFLScience (англ.). Процитовано 5 жовтня 2023.
- ↑ 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].
- The Minimal Superpermutation Problem — Nathaniel Johnston's blog
- Grime, James. Superpermutations - Numberphile (відео). YouTube. Бреді Харан. Процитовано 1 лютого 2018.
- Оригінальні дописи на 4chan, на дошці /sci/, архівовані у warosu.org
- Твіт Робіна Х'юстона, що звернув увагу на пости у 4chan
- Стаття про проблему знаходження коротких суперпермутацій у журналі Quanta