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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Розподіл пермутацій у суперпермутації 3 символів

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

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

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

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

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

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

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

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

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

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

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

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

Верхні межі[ред. | ред. код]

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

Посилання[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Суперпермутація&oldid=42295393