В комбинаторике суперперестановка () для 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 жирным шрифтом):

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

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

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

Другой способ поиска суперперестановок заключается в создании графа, где каждая перестановка является вершиной и соединена ребром. Каждое ребро имеет связанный с ним вес; вес вычисляется путем определения того, сколько символов можно добавить в конец одной перестановки (отбросив такое же количество символов из начала), чтобы получить другую перестановку. Например, ребро от 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. Математическая задача была представлена на имиджборде, в честь аниме «Меланхолия Харухи Судзумии», как «Проблема Харухи»: «Какое наименьшее количество серий Харухи нужно посмотреть, чтобы увидеть оригинальные 14 серий в каждом возможном порядке?».

Доказательство этой нижней границы стало достоянием широкой общественности в октябре 2018 года, после того как математик и специалист по информатике Робин Хьюстон написал об этом в Твиттере. 25 октября 2018 года Робин Хьюстон, Джей Пантон и Винс Ваттер опубликовали более точную версию этого доказательства в OEIS. Опубликованная версия этого доказательства, приписываемая «анонимному пользователю 4chan», появляется в Энген и Ваттер (2021). В частности, для «Проблемы Харухи» (в случае с 14 символами) текущая нижняя и верхняя границы равны 93 884 313 611 и 93 924 230 411 соответственно. Это означает, что для просмотра сериала в любом возможном порядке потребовалось бы около 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 (October 25, 2018). «A lower bound on the length of the shortest superpattern». On-Line Encyclopedia of Integer Sequences.

Примечания

Категория:Комбинаторика Категория:Строковые алгоритмы