Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Распределение перестановок в 3-символьной суперперестановке.

В комбинаторной математике , А superpermutation на п символов является строкой , которая содержит каждую перестановку из п символов в качестве подстроки . Хотя тривиальные суперперестановки могут быть просто составлены из каждой перестановки, перечисленной вместе, суперперестановки также могут быть короче (за исключением тривиального случая n = 1), потому что перекрытие разрешено. Например, в случае n = 2 суперперестановка 1221 содержит все возможные перестановки (12 и 21), но более короткая строка 121 также содержит обе перестановки.

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

1234512341523412534123541231452314253142351423154231245312435124315243125431 2 1345213425134215342135421324513241532413524132541321453214352143251432154321

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

Поиск суперперестановок [ править ]

Схема создания суперперестановки с 3 символами из суперперестановки с 2 символами.

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

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

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

Нижняя и верхняя границы [ править ]

Алгоритм поиска наименьшей суперперестановки для 6 и более символов пока не решен. Однако несколько доказательств постепенно сузили строгие верхние и нижние границы проблемы.

Нижние оценки, или проблема Харухи [ править ]

В сентябре 2011 года , анонимный плакат на науке и математике ( «/ Sci /») доски из 4chan доказал , что наименьшее superpermutation на п символов ( п ≥ 2) имеет по крайней мере длины п ! + ( п - 1)! + ( п - 2)! + n - 3. [4] Что касается японского аниме- сериала «Меланхолия Харухи Судзумии» , проблема была представлена ​​на доске изображений как «Проблема Харухи»: если вы хотите посмотреть 14 серий первого сезона сериала в каждом возможном порядке, какую самую короткую последовательность эпизодов вам нужно будет посмотреть? [5]Доказательство этой нижней границы заинтересовало широкую публику в октябре 2018 года после того, как математик и ученый-компьютерщик Робин Хьюстон написал об этом в Твиттере. [4] 25 октября 2018 года Робин Хьюстон, Джей Пантон и Винс Ваттер опубликовали уточненную версию этого доказательства в Он-лайн энциклопедии целочисленных последовательностей (OEIS). [5] [6] Опубликованная версия этого доказательства, зачисленная на «Анонимный плакат 4chan», опубликована в Engen and Vatter ( 2019 ). [7] В частности, для «Проблемы Харухи» (случай для 14 символов) нижняя граница в настоящее время составляет не менее 93 884 313 611, а верхняя - не более 93 924 230 411. [4]

Верхняя граница [ править ]

20 октября 2018 года, путь адаптации конструкции Аарона Williams для построения гамильтоновых пути через граф Кэлей из симметрической группы , [8] Иган разработал алгоритм для получения superpermutations длиной п ! + ( п - 1)! + ( п - 2)! + ( п −3)! + n - 3. [2] До 2018 г. это были самые маленькие суперперестановки, известные для n ≥ 7. Однако 1 февраля 2019 г. Богдан Коанда объявил, что он нашел суперперестановку для n = 7 длины 5907, или ( n ! + ( n −1)! + ( n−2)! + ( п −3)! + n - 3) - 1, что стало новым рекордом. [2] 27 февраля 2019 года, используя идеи, разработанные Робином Хьюстоном, Иган произвел суперперестановку для n = 7 длиной 5906. [2] Существуют ли аналогичные более короткие суперперестановки для значений n > 7, остается открытым вопросом. Текущая лучшая нижняя граница (см. Раздел выше) для n = 7 по-прежнему составляет 5884.

См. Также [ править ]

  • Superpattern , перестановка, которая содержит каждую перестановку n символов как образец перестановки
  • Последовательность Де Брёйна , аналогичная проблема с циклическими последовательностями

Дальнейшее чтение [ править ]

  • Ashlock, Daniel A .; Тиллотсон, Дженетт (1993), "Построение малых суперперестановок и минимальных инъективных суперструн", Congressus Numerantium , 93 : 91–98, Zbl  0801.05004
  • Анонимный плакат 4chan; Хьюстон, Робин; Пантоне, Джей; Ваттер, Винс (25 октября 2018 г.). «Нижняя граница длины кратчайшего супершаблона» (PDF) . Он-лайн энциклопедия целочисленных последовательностей .

Ссылки [ править ]

  1. ↑ Джонстон, Натаниэль (28 июля 2013 г.). «Неединственность минимальных суперперестановок» . Дискретная математика . 313 (14): 1553–1557. arXiv : 1303.4150 . Bibcode : 2013arXiv1303.4150J . DOI : 10.1016 / j.disc.2013.03.024 . Zbl 1368.05004 . Проверено 16 марта 2014 года .  CS1 maint: обескураженный параметр ( ссылка )
  2. ^ a b c d e f Иган, Грег (20 октября 2018 г.). «Суперперестановки» . gregegan.net . Проверено 15 января 2020 года .
  3. ↑ Хьюстон, Робин (21 августа 2014 г.), «Решение проблемы минимальной суперперестановки», arXiv : 1408.5108 [ math.CO ]
  4. ^ a b c Григгс, Мэри Бет. «Анонимный пост на 4chan может помочь разгадать математическую загадку 25-летней давности» . Грань .
  5. ^ a b Кларрайх, Эрика (5 ноября 2018 г.). "Писатель-фантаст Грег Иган и проблема перестановки анонимных математиков" . Журнал Quanta . Проверено 21 июня 2020 года .
  6. ^ Анонимный плакат 4chan; Хьюстон, Робин; Пантоне, Джей; Ваттер, Винс (25 октября 2018 г.). «Нижняя граница длины кратчайшего супершаблона» (PDF) . OEIS . Проверено 27 октября 2018 года . CS1 maint: обескураженный параметр ( ссылка )
  7. ^ Энген, Майкл; Vatter, Винсент (2021), "Содержит все перестановки", American Mathematical Monthly , 128 (1): 4-24, DOI : 10,1080 / 00029890.2021.1835384
  8. ^ Аарон, Уильямс. «Гамильтоничность орграфа Кэли на симметричной группе, порожденной σ = (1 2 ... n) и τ = (1 2)». arXiv : 1307.2549v3 .

Внешние ссылки [ править ]

  • Задача минимальной суперперестановки - блог Натаниэля Джонстона
  • Грайм, Джеймс. «Суперперестановки - Numberphile» (видео) . YouTube . Брэди Харан . Проверено 1 февраля 2018 . CS1 maint: обескураженный параметр ( ссылка )
  • Сообщение 4chan на / sci / , заархивировано на warosu.org
  • Твит Робина Хьюстона, который привлек внимание к посту 4chan