Суперперестановка

Необходимо проверить качество перевода, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его.

В комбинаторике суперперестановка (с англ. — «Superpermutation») для 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 жирным шрифтом)^[1]:

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

Одним из наиболее распространенных алгоритмов создания суперперестановки порядка n является рекурсивный алгоритм. Сначала суперперестановка порядка n − 1 разбивается на отдельные перестановки в порядке их появления в суперперестановке. Каждая из этих перестановок затем помещается рядом с собственной копией, а между двумя копиями добавляется n-й символ. Наконец, каждая результирующая структура помещается рядом друг с другом, и все соседние идентичные символы объединяются^[2].

Например, суперперестановка порядка 3 может быть создана из одной, содержащей 2 символа; начиная с суперперестановки 121 и разбивая её на перестановки 12 и 21, перестановки копируются и размещаются как 12312 и 21321. Они помещаются вместе, чтобы создать 1231221321, а идентичные соседние 2 в середине объединяются, чтобы создать 123121321, что действительно является суперпереходом порядка 3. Этот алгоритм приводит к кратчайшей возможной суперперестановке для всех n, меньших или равных 5, но становится длиннее кратчайшей возможной по мере увеличения n сверх этого значения^[2].

Другой способ поиска суперперестановок заключается в создании графа, где каждая перестановка является вершиной и соединена ребром. Каждое ребро имеет связанный с ним вес; вес вычисляется путем определения того, сколько символов можно добавить в конец одной перестановки (отбросив такое же количество символов из начала), чтобы получить другую перестановку^[2]. Например, ребро от 123 до 312 имеет вес 2, потому что 123 + 12 = 12312 = 312. Любой гамильтонов граф через созданный граф является суперперестановкой, и задача нахождения пути с наименьшим весом становится разновидностью задачи коммивояжёра. Первый случай суперперехода, меньшего длины 1! + 2! + … + n! был найден с помощью компьютерного поиска по этому методу Робином Хьюстоном.

В сентябре 2011 года анонимный пользователь на доске Science & Math («/sci/») на 4chan доказал, что наименьшая суперперестановка для n символов (n ≥ 2) имеет длину не менее n! + (n−1)! + (n−2)! + n − 3^[3]. Математическая задача была представлена на имиджборде, в честь аниме «Меланхолия Харухи Судзумии», как «Проблема Харухи»^[4][5]: «Какое наименьшее количество серий Харухи нужно посмотреть, чтобы увидеть оригинальные 14 серий в каждом возможном порядке?».

Доказательство этой нижней границы стало достоянием широкой общественности в октябре 2018 года, после того как математик и специалист по информатике Робин Хьюстон написал об этом в Твиттере^[3]. 25 октября 2018 года Робин Хьюстон, Джей Пантон и Винс Ваттер опубликовали более точную версию этого доказательства в OEIS^[6][7]. Опубликованная версия этого доказательства, приписываемая «анонимному пользователю 4chan», появляется в Энген и Ваттер (2021)^[8]. В частности, для «Проблемы Харухи» (в случае с 14 символами) текущая нижняя и верхняя границы равны 93 884 313 611 и 93 924 230 411 соответственно^[3]. Это означает, что для просмотра сериала в любом возможном порядке потребовалось бы около 4,3 миллиона лет^[9].

20 октября 2018 года, адаптировав конструкцию Аарона Уильямса для построения гамильтонов граф через граф Кэли симметричной группы^[10], автор научной фантастики и математик Грег Иган разработал алгоритм для получения суперпереходов длины 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 (October 25, 2018). «A lower bound on the length of the shortest superpattern». On-Line Encyclopedia of Integer Sequences.