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

У комбінаториці, суперпермутація 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 символів

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

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

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

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

У вересні 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 (PDF). Інтерактивна енциклопедія цілочислових послідовностей.

Примітки

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 (PDF). 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].

Посилання

• The Minimal Superpermutation Problem — Nathaniel Johnston's blog
• Grime, James. Superpermutations - Numberphile (відео). YouTube. . Процитовано 1 February 2018.
• Оригінальні дописи на 4chan, на дошці /sci/, архівовані у warosu.org
• Твіт Робіна Х'юстона, що звернув увагу на пости у 4chan
• Стаття про проблему знаходження коротких суперпермутацій у журналі Quanta