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

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

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

Доведено, що при 1 ≤ n ≤ 5, найменша суперпермутація n символів має довжину 1! + 2! + … + n!. Довжини перших чотирьох найменших суперпермутацій: 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$ — рекурсивний алгоритм. Спочатку, суперпермутація порядку $n-1$ ділиться на свої окремі перестановки у тому порядку, в якому вони з'явились у самій суперпермутації. Потім кожна з цих пермутацій розташовується після самої себе, та між ними двома додається n-ий символ. Зрештою, кожний з утворених таким чином рядків розташовується один після одного, та всі ідентичні символи об'єднуються.

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

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

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

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

Для випадку «Проблеми Харухі» (суперпермутація при 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.

Див. також

• Послідовність де Брейна, подібна проблема, але з циклічними послідовностями

Література

• Шаблон:Citation
• Шаблон:Cite journal

Посилання

• The Minimal Superpermutation Problem — Nathaniel Johnston's blog
• Шаблон:Cite web
• Оригінальні дописи на 4chan, на дошці /sci/, архівовані у warosu.org
• Твіт Робіна Х'юстона, що звернув увагу на пости у 4chan
• Стаття про проблему знаходження коротких суперпермутацій у журналі Quanta