Загадочный математический гений и писатель продвигают решение задачи о перестановке

https://www.quantamagazine.org/sci-fi-writer-greg-egan-and-anonymous-math-whiz-advance-permutation-problem-20181105/
  • Перевод

Новое доказательство за авторством австралийского писателя-фантаста Грега Игана и доказательство от 2011 года, анонимно опубликованное в сети, признали значительными прорывами в области изучения загадки, которую математики исследуют уже 25 лет




16 сентября 2011 года один фанат аниме опубликовал на форуме математический вопрос 4chan, касающийся культового сериала "Меланхолия Харухи Судзумии". Первый сезон шоу, где были и путешествия во времени, показали в порядке, отличном от хронологического, а во время дальнейшего показа и выпуска на DVD порядок эпизодов снова меняли. В интернете фанаты спорили о том, в каком порядке лучше смотреть сериал, а автор вопроса поинтересовался: если бы зрители захотели посмотреть сериал во всех возможных порядках, какое количество эпизодов было бы в кратчайшем их списке? [имеется в виду список, в котором можно найти любую последовательность эпизодов / прим. перев.]

Менее чем за час один аноним привёл ответ на вопрос – не полное решение, но нижнюю границу на необходимое количество эпизодов. Из его рассуждения, применимого к любому количеству эпизодов, следовало, что для первого сезона Харухи, состоявшего из 14 серий, зрителям пришлось бы посмотреть не менее 93 884 313 611 серий подряд, чтобы изучить все возможные перестановки. «Изучите доказательство на предмет недостатков, которые я мог бы пропустить», — написал автор ответа.

Доказательство семь лет оставалось незамеченным в математическом сообществе – оказалось, что в тот момент его заметил только один профессиональный математик, и он не изучил его достаточно тщательно. Однако внезапно в прошлом месяце австралийский писатель-фантаст Грег Иган доказал наличие нового верхнего предела на необходимое количество эпизодов. Открытие Игана заново подняло интерес к задаче и привлекло внимание к записи, касавшейся нижней границы, от 2011 года. Оба эти доказательства сейчас расцениваются как значительные прорывы в деле изучения загадки, которую математики исследуют не менее 25 лет.

Математики быстро проверили верхнюю границу от Игана, которая, как и нижняя граница, применима к последовательностям любой длины. Затем Робин Хьюстон, математик из компании Kiln, занимающейся визуализацией данных, и Джей Пэнтон из Университета Маркетта из Милуоки независимо подтвердили работу анонимного автора с 4chan. «Много усилий ушло на проверку правильности этой гипотезы», — сказал Пэнтон, поскольку ключевые идеи доказательства не были выражены достаточно чётко.

И теперь Хьюстон и Пэнтон, совместно с Винсом Вэтером из Флоридского университета написали формальную работу. В ней они указали первого автора как «анонимный постер 4chan».

«Странность ситуации в том, что это очень элегантное доказательство ранее неизвестного факта появилось в таком маловероятном месте», — сказал Хьюстон.

Города перестановок


Если в сериале всего три эпизода, существует шесть возможных способов их посмотреть: 123, 132, 213, 231, 312 и 321. Их можно склеить вместе и сделать список из 18 эпизодов, включающих в себя каждый вариант порядка. Однако существует и более эффективный способ склейки: 123121321. Такая последовательность, содержащая все перестановки набора из n символов, называется сверхперестановкой.

В 1993 году Дэниел Эшлок и Дженет Тилотсон обнаружили, что при изучении кратчайших сверхперестановок для различных значений n быстро начинают проявляться факториалы – те же самые значения, записанные в виде n!, то есть, перемножения всех чисел от 1 до n (к примеру, 4! = 4 * 3 * 2 * 1).

Если в вашем сериале всего 1 эпизод, то длина кратчайшей сверхперестановки будет равна 1! (также известная, как старая добрая единица). Для сериала из двух эпизодов кратчайшая сверхперестановка (121) имеет длину 2! + 1!.. Для трёх эпизодов (пример выше) длина оказывается равной 3! + 2! + 1!, а для четырёх эпизодов (123412314231243121342132413214321) она будет 4! + 3! + 2! + 1!.. Правило факториалов стало общепринятым (хотя никто не мог доказать, что оно верно для всех n), и позже математики подтвердили его для n = 5.

Затем в 2014 году Хьюстон поразил математиков, показав, что для n = 6 правило перестаёт работать. Правило предсказывает, что для просмотра шести эпизодов всеми возможными способами потребуется 873 эпизода, но Хьюстон нашёл способ сделать это за 872. И поскольку существует простой способ превратить короткую сверхперестановку для n символов в короткую сверхперестановку для n+1 символов, пример Хьюстона означал, что правило факториалов не работает и для всех n > 6.

Построение Хьюстона превращает задачу сверхперестановки в знаменитую задачу коммивояжёра, которая ищет кратчайший путь через несколько городов. Конкретно, сверхперестановки связаны с «асимметричной» задачей коммивояжёра, в которой каждый путь между двумя городами имеет свою цену (не обязательно одинаковую в обоих направлениях), а целью является нахождение наиболее дешёвого пути через все города.

Это превращение легко понять: представим, что каждая перестановка – это город, и представим себе путь от каждой перестановки до каждой другой перестановки. В задаче сверхперестановки нам нужна кратчайшая последовательность цифр, в которой присутствуют все перестановки, поэтому нашей целью является пройти через все перестановки так, чтобы добавить к начальной перестановке как можно меньше чисел. Мы объявляем, что стоимость каждого пути просто равна количеству цифр, которое нам необходимо присоединить к концу первой перестановки, чтобы получить вторую. В примере с n = 3 путь от 231 до 312 стоит $1, поскольку нам нужно добавить только 2 к концу 231, чтобы получить 312, а путь от 231 до 132 стоит $2, поскольку нам надо добавить 32. В такой формулировки наиболее дешёвый путь через все города напрямую соответствует кратчайшей сверхперестановке.



Такое превращение означало, что Хьюстон мог направить все возможности алгоритмов решения задачи коммивояжёра на задачу сверхперестановки. Эта задача известна своей принадлежностью к классу NP-сложных, что означает отсутствие существования эффективного алгоритма, способного решать её в общем случае. Однако существуют алгоритмы, способные эффективно решать некоторые разновидности задачи, а другие алгоритмы могут выдавать неплохие примерные решения. Хьюстон использовал один из последних, чтобы выдать сверхперестановку длиной в 872 цифры.

Поскольку он выдал лишь приблизительное решение, оно даже может быть не самой идеальной сверхперестановкой. Математики сейчас проводят объёмный вычислительный поиск кратчайшей сверхперестановки из 6 символов, сказал Пэнтон. «Мы знаем, что наши поиски закончатся за конечное время, но не знаем, займёт это неделю или миллион лет, — сказал он. – Индикатора выполнения там нет».

Неправильный порядок


К моменту появления работы Хьюстона, анонимный пост на 4chan сидел в своём уголке интернета почти три года. Один математик, Натаниэль Джонстон из Университета Маунт-Эллисон, заметил копию этого поста на другом сайте через несколько дней после того, как эта запись появилась – и не потому, что он был любителем аниме, но потому, что он вводил в Google разные запросы, связанные с сверхперестановками.

Джонстон прочитал доказательство и оно показалось ему достоверным, но он не стал тратить силы на тщательную проверку. В то время математики считали, что формула факториалов для сверхперестановок была, скорее всего, верной, и когда вы считаете, что вам известен точный ответ на вопрос, нижняя граница оценки вас интересует слабо. Иначе говоря, эпизоды сериала про сверхперестановки шли не в том порядке.

После этого Джонстон упоминал нижнюю границу на паре веб-сайтов, но «я не думаю, что кто-то обратил на это особое внимание», — сказал он.

Затем 26 сентября 2018 математик Джон Баез из Калифорнийского университета в Риверсайде опубликовал в твиттере пост по поводу открытия Хьюстона от 2014 года, в рамках серии твитов по поводу очевидных математических закономерностей, которые перестают работать.

Прим. перев.: там была не такая уж большая серия твитов, всего три. Два остальных тоже интересны сами по себе, хотя не имеют отношения к данной статье. В одном говорится о том, что 6 – это самое популярное расстояние между двумя соседними простыми числами для всех простых чисел меньших, чем 17 427 000 000 000 000 000 000 000 000 000. А потом эта закономерность вдруг перестаёт работать! Второе демонстрирует следующую связь интегралов, тригонометрических функций и числа π



Но только для n < 9,8 × 1042!


Его твит привлёк внимание Игана, изучавшего математику несколько десятилетий назад, до того, как началась его карьера признанного писателя-фантаста (его первая успешная повесть, по счастливой случайности, называлась «Город перестановок»). «Я никогда не переставал интересоваться математикой», — написал Иган по почте.

Иган заинтересовался, возможно ли создать сверхперестановку ещё более короткую, чем у Хьюстона. Он погрузился в изучение литературы о том, как создавать короткие пути в сетях перестановок, и через несколько недель нашёл то, что ему требовалось. За пару дней он вывел новую верхнюю границу на длину кратчайшей сверхперестановки из n символов: n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3. Она похожа на формулу факториалов, из которой исключили много членов.

«Это полностью разбило предыдущую верхнюю границу», — сказал Хьюстон.

Нижняя граница автора поста на 4chan была соблазнительно близка к новой верхней границе: n! + (n – 1)! + (n – 2)! + n – 3. После публикации результата Игана Джонстон напомнил математикам о доказательстве анонимного автора, и Хьюстон с Пэнтоном вскоре доказали его корректность. Как и в работе Хьюстона, новая нижняя и верхняя границы подходят к сверхперестановкам с точки зрения задачи коммивояжёра: нижняя граница показывает, что путь через все города должен пройти через некоторое минимальное количество путей стоимостью более $1, а верхняя граница создаёт особый путь для каждого n, использующий только соединения стоимостью в $1 и $2.

Теперь исследователи пытаются свести верхнюю и нижнюю границы вместе, и найти единую формулу, решающую задачу сверхперестановки. «Вероятно, в итоге люди всё же разгадают эту загадку, — предсказал Баез. – Сейчас уже всё выглядит неплохо».

Для фанатов Харухи решение Игана даёт точную инструкцию о том, как просмотреть все возможные варианты порядка первого сезона, используя всего 93 924 230 411. Начинать просмотр можно уже сегодня, или можно подождать, пока математики смогут ещё урезать это число. Нижняя граница от анонимного автора доказывает, что это урезание не сможет сэкономить им больше 40 млн эпизодов – однако, этого достаточно, чтобы начать готовиться ко второму сезону.
Поделиться публикацией
Комментарии 124
    –67
    Даже теология привносит больше пользы чем математика.
      +26
      Даже теология привносит мне больше пользы чем математика.

      я у вас опечатку поправил, можете не благодарить.
      Понятно, что у вас — так, но в жизни множество вещей, профессий и отраслей, где без математики — вообще никак.
        +13
        image
          +16
          Ваша правда. Ни один запуск ракеты не обходится без освящения.
            +1
            Вроде, это только наша национальная традиция. Поправьте, если ошибаюсь.
            Хьюстон, у нас проблемы, взлёт откладывается, кадило забыли!
              0
              Some people at NASA do. The most famous example is the Alan Shepard prayer: “Dear God, please don't let me fuck up.” Alan B. Shepard was the very first American astronaut to fly a space mission.
            +6
            А я завидую математикам черной завистью — они решают такие увлекательные задачи. Вот бы мне быть хоть на 10% таким же умным.
              –7

              У нас тебе кушать было б нечего, будь ты математиком. А программистом можно на жизнь хоть как-то зарабатывать.

                +4
                Никто не мешает совмещать :)
                  +3
                  Мешает ограниченность времени и ментальных ресурсов.
                    +4
                    Ну, смотря как к этому подходить. При некотором уровне абстракции программирование – математика и многое из математики применимо в программировании (и наоборот).
                    Я бы даже сказал, что IT как раз та сфера, где совмещать математику и инженерию проще всего.
              +10
              Стухла молодёжь совсем. Никакой тонкости и изящества, одна толстота.
              Печаль.
                –1
                Тащемта он больше похож на откато-распильного кремлебота по заказу «надо молодежи полезные комментарии в тырнеты пописать о разрухе в айти-сфере, глядишь заводы заполним, чего там айтишное есть в стране, TM?», чем на саму молодежь. Поанализируйте другие его комменты — настолько отвратительно толсто быть не может совсем.
                  +12
                  > настолько отвратительно толсто быть не может совсем.
                  Недавно в интернете?
                    +1
                    Давненько уже.
                    Профит от троллинга на сайте с троллингоустойчивой ЦА нулевой. Любой школьник это осознает. Да и выборка странная КМК — тролли обычно идут в места понажористей, у него из таковых только коммент в пост одного российского поисковика с содержанием сравнения с одним нероссийским. И это после событий с попыткой честного приобретения этого самого российского поисковика российским банком.
                    А вот комменты с содержанием «снова облажались макдонольдсовые» — неплохой маячок.
                      0

                      Интересно, кто ему инвайт дал...

                        +2
                        Давно уже без инвайта можно регаться. Как минимум тогда, когда зарегался я — дату можете в профиле увидеть.
                        С подключеньицем.
                          0
                          Это обычный read&comment, прошедший порог отключения премодерации.
                          0
                          Профита от любого троллинга нет никакого, это шутка, над которой смеется пошутивший, а не услышавший.
                    +4
                    Как одной фразой слить себя на техническом ресурсе…
                      +13
                      Хабр относится к техническим ресурсам примерно как техническая вода к питьевой
                        +1

                        Ну какой есть. По-моему, один из лучших, если не лучший, на просторах рунета.

                          +7
                          Он перестал таким быть, как только открыли инвайт для всех.
                            +7
                            Он перестал таким быть, как только токсичность коммьюинити начала выгонять скромных и ранимых инженеров и программистов с сайта :)

                            Хотя, конечно, не исключено и влияние инвайтов для всех.
                              +1
                              Он перестал таким быть, как только токсичность коммьюинити начала выгонять скромных и ранимых инженеров и программистов с сайта :)

                              8-10 лет назад?
                                +3
                                Ну где-то так, да :)
                                  –1
                                  Да ниче он не перестал — просто комменты если не нравяться — не читайте :) А статей и сейчас много интересных, особенно для ИТшников.
                                    +1
                                    Мне вот лично сложно выцепить прям интересную-интересную статью на Хабре. В основном разные околоайтишные или how-to по «модным» языкам.

                                    Позиция «не нравится – не читай» для такого ресурса как Хабр в принципе не приемлема.
                                0

                                Интересно, возможно ли создать сайт для скромных и ранимых инженеров и программистов, такой, чтобы у тролей вообще не было возможности прийти туда и их выгнать.

                                  0
                                  Ну, Хабр можно было бы еще спасти, измени они систему хабракармы. Чтобы не было задавливание альтернативного мнения ограничениями на сайте.
                                  (имхо)

                                  Но это совсем оффтопик и предлагаю все же вернуться к статье.
                                    +1
                                    Для меня HN стал таким сайтом. Не знаю, как им это удаётся, но я чувствую себя там комфортно в отличие от хабра, на котором я даже писать могу то ли раз в сутки, то ли около того.
                                      +1
                                      Дайте пожалуйста ссылочку в личку, а то я тут недавно высказал свое мнение по поводу Линукса и вирусов и меня заминусили, хотя никого и не обижал и не троллил. Иногда кажется что хабр населен задротами — неудачниками, которые стараются за счёт минусов самоутвердиться.
                            +1
                            Хабр относится к техническим ресурсам примерно как техническая вода к питьевой

                            Угу, пришёл напиться, а там уже ноги помыли.
                            По этому всегда читаю шапку комментариев, до мутной воды.
                            0
                            Не правда. Он к этому 19 комментариев шёл!
                              +2

                              Есть подозрение, что комментатор имел ввиду теологические вопросы Харухизма, которые и привели к появлению гипотезы о нижней границе.
                              Но был не понят неискушённой в альтернативных религиозных веяниях аудиторией.

                              +12
                              Вау! Главные качества нашего инженера:

                                +3

                                Порядок в списке качеств по убыванию значимости?)
                                <шутка про приоритеты>

                                  0
                                  Угу, главное — вера, а прочее можно и измениь лёгким росчерком пера ;-)
                                  0
                                  О, мифический притесняемый WASP нашёлся?
                                  +2
                                  Какой-то странный Вы программист.
                                  Я сомневаюсь, что Вам математика никогда не пригождалась как программисту.
                                  Не нравится — не пишите, у всех вкусы разные.
                                    0

                                    Замечу, что для многих задач действительно достаточно арифметики уровня начальных классов.

                                      0
                                      Да, есть либы которые все решают.
                                      По поводу математики для программистов уже статья была.

                                      habr.com/company/yandex/blog/239339

                                      Понятно, что не вся математика нужна, а какие то определенные области, и все зависит от выполняемой задачи.

                                      Не нужно знать всё, нужно свободно ориентироваться и усвоить что-то новое когда понадобится.

                                      Тут комбинаторика — и я считаю, что каждому хорошему программисту это полезно.
                                    +12
                                    Я прекрасно живу без религиозных мозговых слизней. И отлично буду жить, если все религиозные люди вместе с «пропагандитами» их религий покинут планету прямо немедленно в сию же секунду (улетят в прекрасное будущее, в рай и т.д.). Скорее всего, даже гораздо лучше.

                                    А вот если исчезнут математики, учителя математики и математика, как наука, то жить мы будем где-то между первобытно общинным строем и первыми поселениями из веток и досок. Минус вся физика-химия-медицина-строительство-айти и много-много чего еще.

                                    P.S. И храмы ваши все тоже придется разобрать, там математики и геометрии при строительстве просто дофига. И пирамиды придется раскатать. Вручную.

                                    P.P.S. Но спасибо вам за то, что еще раз показали, почему религию столь яростно демонтировали в 1917 году. Во-первых власть, во-вторых яростная религиозность обратно коррелирует с интеллектом и общим развитием страны.

                                    image
                                      0
                                      Религиозный оффтоп про 1917-й год
                                      Но спасибо вам за то, что еще раз показали, почему религию столь яростно демонтировали в 1917 году.

                                      В 1917 году уничтожали одну религиозную систему, заменяя другой, сейчас они сливаются вместе т.к. близкородственны.
                                        0
                                        Но спасибо вам за то, что еще раз показали, почему религию столь яростно демонтировали в 1917 году. Во-первых власть, во-вторых яростная религиозность обратно коррелирует с интеллектом и общим развитием страны.
                                        Наверное, чтобы через 70 лет ту же страну накрыло сектами, а из телевизора кашпировский заряжал им воду?
                                          0
                                          Это Чумак заряжал, а Кашпировский рассасывал и затягивал.
                                          Ну нельзя же так путать эпохальные прорывные технологии в телемедицине.
                                      +1
                                      Для фанатов Харухи решение Игана даёт точную инструкцию о том, как просмотреть все возможные варианты порядка первого сезона, используя всего 93 924 230 411.

                                      Так я не понял, решение дает конкретную суперперестановку или все-таки количество ее элементов?

                                        +2
                                        Я тоже не понял. В статье написано, что уже можно брать готовую перестановку и смотреть все серии. Но при этом приводятся формулы, с помощью которых пожно вычилисть только количество элементов для нижней и верхней границы.
                                          +1

                                          Расходимся, нас на… обманули. ©

                                          +1
                                          насколько я понял — это не решение суперперестановки, а оценка решения сверху (т.е. настоящее решение может быть равно ему или быть короче).
                                          При этом оно позволяет вычислить суперперестановку для этого количества элементов (если вы вдруг захотите начать их смотреть — у Игана есть описание алгоритма и даже код на С написан для генерирования).
                                          0
                                          Так все таки стоит смотреть сериал и в каком прядке?
                                            0
                                            я сам смотрел в таком порядке:
                                            1) читаем новеллу
                                            2) смотрим сериал.

                                            PS: мое личное мнение — лучше в хронологическом.
                                              +1
                                              Как издавался. Сначала первый сезон в том порядке как он выходил, потом второй также как он выходил. Т.к. оригинальная трансляция второго сезона включает первый в порядке внутренней хронологии.
                                              0
                                              Что-то мне подумалось: если задача переходит в задачу коммивояжёра (с ценой), могут ли на практике (при просчете маршрутов) возникать ситуации, когда равнозначных ценовых решений несколько? Статью Эгана нашел с кодом: www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html
                                              Код, кстати, для n 5 генерирует подстроку длиной 154
                                                0
                                                  0
                                                  Да. 153. Мне непонятно: при n = 3, n = 4 наблюдается симметрия, т.е. алгоритм доходит до какой-то точки, затем фактически движется обратно — отражение. Я так понял, при n > 6 симметрия пропадает, и это одна из главных проблем.
                                                  Кстати, код Эгана и для n = 4 генерирует 34, а должен 33 вроде бы.
                                                  Я думал над алгоритмом, как бы я его писал: циклический сдвиг изначальной перестановки до замыкания с записью в файл/буфер, далее проверка последней перестановки, чтобы понять, какое число подставить для продолжения цепочки… да еще и так, чтобы перестановки не повторялись. Трудоемко получается, надо проверять все что было сгенерировано ранее, дабы не словить повторы или не нагенерировать лишнего.
                                                  Но что-то мне кажется (только кажется пока), что алгоритм Джонсона Троттера для перестановок тут бы пригодился бы (там как раз циклический сдвиг)… но не уверен.
                                                    0
                                                    для n=4

                                                    1234123142134214324132431243214231 — код Эгана
                                                    1234123142_31243121342132413214321 — oeis.org/A180632

                                                    Может Эган ошибку где-то совершил. ("_" вставил для удобства просмотра, пробел не помогает)
                                                      0
                                                      Написал незамысловатый код на С++, длина совпадает:
                                                      Код
                                                      #include <iostream>
                                                      #include <string>
                                                      
                                                      struct Node {
                                                      	int value;
                                                      	Node* next;
                                                      };
                                                      
                                                      // rotate and append c nodes from root to the end
                                                      void firstToLast(Node* &root, int c) {
                                                      	Node* tail = nullptr;
                                                      	Node* node;
                                                      
                                                      	// grow a tail  
                                                      	for(int i=0;i<c;i++) {
                                                      		node = root;
                                                      		root = root->next;
                                                      		node->next = tail;
                                                      		tail = node;
                                                      	}
                                                      
                                                      	node = root;
                                                      
                                                      	// find the end
                                                      	while(node->next) {
                                                      		node = node->next;
                                                      	}
                                                      
                                                      	// append to the end
                                                      	node->next = tail;
                                                      }
                                                      
                                                      int main(int argv, char** argc)
                                                      {
                                                      	using namespace std;
                                                      	int n = 4;
                                                      	string result;
                                                      
                                                      	// count factorial of n
                                                      	int factorial = 1;
                                                      	for(int i=2;i<=n;i++) 
                                                      		factorial *= i;
                                                      	
                                                      	Node* next;
                                                      	Node* last;
                                                      	Node* node = nullptr;
                                                      	Node* root = node;
                                                      
                                                      	for(int i=n;i>0;i--) {
                                                      		next = node;
                                                      		node = new Node();
                                                      		node->value = i;
                                                      		node->next = next;
                                                      	}
                                                      
                                                      	root = node;
                                                      
                                                      	int sum = n;
                                                      
                                                      	for(int i=1;i<=factorial;i++) {
                                                      		while(node) {
                                                      			cout << node->value;// << " ";
                                                      			if (!node->next) break;
                                                      			node = node->next;
                                                      		}
                                                      
                                                      		cout << endl;
                                                      
                                                      		// check divisibility
                                                      		int m = n;
                                                      		int mm = m;
                                                      
                                                      		while (m > 0) {
                                                      			if (i%mm == 0) {
                                                      				cout << "==========" << endl;
                                                      				mm *= --m;
                                                      			} else {
                                                      				sum+=n-m+1;
                                                      				firstToLast(root, n-m+1);
                                                      				break;
                                                      			}
                                                      		}
                                                      		//*/
                                                      		node = root;
                                                      	}
                                                      
                                                      	cout << "sum=" << sum << endl;
                                                      
                                                      	return 0;
                                                      }


                                                      github.com/tigertv/superpermutation

                                                      Результат для n=4
                                                      1234
                                                      2341
                                                      3412
                                                      4123
                                                      ==========
                                                      2314
                                                      3142
                                                      1423
                                                      4231
                                                      ==========
                                                      3124
                                                      1243
                                                      2431
                                                      4312
                                                      ==========
                                                      ==========
                                                      2134
                                                      1342
                                                      3421
                                                      4213
                                                      ==========
                                                      1324
                                                      3241
                                                      2413
                                                      4132
                                                      ==========
                                                      3214
                                                      2143
                                                      1432
                                                      4321
                                                      ==========
                                                      ==========
                                                      ==========
                                                      ==========
                                                      sum=33

                                                        0
                                                        Как я понял, код только длину считает?
                                                        Кстати, я не заметил сразу, что
                                                        число суперперестановок = факториал числа + число суперперестановок от предыдущего. Т.е. для n = 5 120+33 и т.д. только 872 все ломает
                                                          0
                                                          (В качестве шутки). Подумалось вчера, какова верхняя граница строки для нормативного словаря русского языка, например, Ожегова. = ) коткатокно — кот, откат, каток, ток, окно, но
                                                            0
                                                            Как я понял, код только длину считает?
                                                            Да, длину считает. Теперь и строку формирует — обновил код в репозитории.
                                                            Кстати, я не заметил сразу, что
                                                            число суперперестановок = факториал числа + число суперперестановок от предыдущего.
                                                            Я тоже не заметил.)
                                                            (В качестве шутки). Подумалось вчера, какова верхняя граница строки для нормативного словаря русского языка, например, Ожегова. = ) коткатокно — кот, откат, каток, ток, окно, но
                                                            Ну тут вообще вариантов целая куча, учитывая, что длина слов разная, и еще отсекать нужно неправильные наборы cлов.
                                                              0
                                                              Класс! Очень компактный код получился и вроде бы довольно понятный.
                                                              Всего 120 строк. Начинаю жалеть, что не знаю С++ (и, видимо, ООП, раз там node, struct… Не посмотрел на ваш код и понял, что программист бы из меня не вышел: я бы если написал так, то наверное, неделю сидел, обдумывая)
                                                              Интересно, почему у Эгана за 600 строк переваливает.
                                                              Форкнул себе.
                                                              При n = 7 там симметрия сохраняется.
                                                              Интересно, как тот человек сократил до 872 для n 6
                                                                0
                                                                Эган — математик и писатель, а не программист. Ему — можно.
                                                                  0
                                                                  Первый форк!
                                                                  Думаю, что там еще можно улучшения наделать.(дублирование кода, уменьшить проверку на деление).
                                                                  Код не ООП, структуры и в Cи есть.
                                                                  Можно на Си переписать, код не сильно будет отличатся.
                                                                  Заменить iostream на stdio, new на какой-нибудь malloc, cout на printf.

                                                                  Ну код у Эгана также, почему-то, неправильные ответы выдавал. Видимо, где-то ошибка закралась. Может писал для случая 872. У меня такого нет, я пока еще паттерн не понял.
                                                                  Вот тут еще код есть какой-то на Python и еще на чем-то.
                                                                  arxiv.org/abs/1408.5108

                                                                  Вот такое число нужно сравнивать 872
                                                                  arxiv.org/src/1408.5108v1/anc/superperm-6-866.txt
                                                                    0
                                                                    Я вникаю в код, пока не все понял. То, что осознал пока: создается структура для n нод, потом от исходной перестановки (если я верно понял) справа налево прокручиваются варианты, то, что в последнем знаке добавляется к общей строке, так до исходной. Не могу понять, когда алгоритм доходит до предела одной ноды, как происходит выбор следующей. Как проверяется, что надо взять следующий фрагмент цепочки не с единицы, а с двойки…
                                                                    Видимо, мне пока надо его на бумаге еще обдумывать.
                                                                      0
                                                                      Да, в начале создается цепочка или односвязный список. Далее производится переброс узлов с головы(root лучше бы head назвал) c вращением. Сколько узлов перебрасывать определяется в зависимости от делимости номера текущего переброса. Cначала делишь на n, если не делится нацело, то перебрасываешь только один узел, если делится, то проверяешь делимость на n(n-1) если не делится — перебрасываешь 2, если делится, то проверяешь делимость n(n-1)(n-2)… ну и так далее. Так формируются цепочки которые идут последовательно. А чтоб получить результирующую строку, нужно сначала добавить значения из узлов первой цепочки, а затем добавлять только те узлы которые идут на переброс слева направо.
                                                                        0
                                                                        Огромная благодарность. Более или менее понял. Я со списками не работал никогда, буду знать, чего доучивать.
                                                                      0
                                                                      Еще мысли после чтения доказательства:
                                                                      www.njohnston.ca/2014/08/obvious-does-not-imply-true-the-minimal-superpermutation-conjecture-is-false
                                                                      Если по формуле из статьи смотреть (n-2) + (n-1)! + n! для n=4 нижняя граница 32, а не 33.
                                                                      И для n=3 нижняя граница = 8. И вдруг неожиданно это приобретает смысл, если обратить внимание на то, что мы работает с кольцом (не знаю, какой термин употребить, имеется в виду замкнутая последовательность). Тогда для n=3 12312132 последняя единица берется из начала. В общем, изначально кольцо представлено, как цепочка. И это надо учитывать. И тогда все верно: 8, 32, 152, 872.
                                                                          0
                                                                          Аноним фибоначчи использовал

                                                                          Пост анонима
                                                                          I think I solved it.

                                                                          First calculate the max string which is the number of permutations multiplied by n.
                                                                          Then divide the max string by n — 1
                                                                          Then add to the answer the fibonacci number located at 2(n-3)

                                                                          int max_string = n! * n;
                                                                          int answer = max_string / (n — 1);
                                                                          answer += fib(2(n-3));

                                                                          Example for n = 5;

                                                                          max_string = 5! * 5 = 600
                                                                          answer = 600 / 4 = 150
                                                                          answer += fib(2(5-3)) = fib(4) = 3
                                                                          answer = 153

                                                                          Here is the first 14 using this method:

                                                                          2 -> 3
                                                                          3 -> 9
                                                                          4 -> 33
                                                                          5 -> 153
                                                                          6 -> 872
                                                                          7 -> 5901
                                                                          8 -> 46135
                                                                          9 -> 408384
                                                                          10 -> 4032377
                                                                          11 -> 43909467
                                                                          12 -> 522549784
                                                                          13 -> 6745945965
                                                                          14 -> 93884331311
                                                                            0
                                                                            Вроде бы я понял. Два дня промучился, а всего лишь надо было
                                                                            посмотреть на картинку.

                                                                            Тогда на мой взгляд алгоритм такой (если не напутал):
                                                                            1) Крутим до n, например n = 3
                                                                            123
                                                                            231
                                                                            312
                                                                            2) Проверяем делится ли номер итерации нацело на n (вроде также как в написанном коде у MaxVetrov и Эгана)
                                                                            Делится, тогда идем по хвосту слева направо (два прохода, чтобы снова не делилось нацело )
                                                                            3) То, что осталось — идет в начало, перевернутый хвост идет в конец.
                                                                            4) Снова крутим.
                                                                            213
                                                                            132
                                                                            321
                                                                            5) Дошли до факториала. Остановка.

                                                                            Проверил на n=4, n=5 — все верно.
                                                                            Тогда, чутье подсказывает, что можно без struct, но пока не на сто процентов уверен.
                                                                              0
                                                                              Можно использовать std::list, хотя это тот же набор Node, c множеством операций над ними.

                                                                              Я понял вашу мысль на счет кольца, перекидывать элементы не нужно.
                                                                              Нужно только отслеживать какая итерация, делится ли она на n cначала. (for-loop)
                                                                              А потом как-то нужно из этого кольца вытащить 2 узла, перевернуть, и опять вставить в кольцо и продолжить итерацию.
                                                                              Можно и так, на выходе получаем тоже самое.(может скорость быстрее — может нет, проверять надо).

                                                                              Меня вот заинтересовало, почему для 1<n<4 существует единственная комбинация(не считая комбинации начинающиeся не на 123...n),
                                                                              а для n=5 их аж восемь www.njohnston.ca/superperm5.txt
                                                                              Возможно и для n=5, есть более короткая комбинация.
                                                                              Cкажем, длиною 152, а не 153, как везде указано.
                                                                                0
                                                                                Похоже, что скорость генерации перестановок быстрее. Алгоритм генерации я сделал, но последовательность пока не собрал.
                                                                                Но можно уже протестировать:
                                                                                Код
                                                                                Похоже, и правда быстрее. Если еще оптимизировать. Но там substr и strrev но они довольно быстры в php.
                                                                                  0
                                                                                  А быстрее чем что? У вас же код на php.

                                                                                  PS. У вас в репозитории мой старый код лежит. Я его уже обновил, он работает быстрее.
                                                                                    0
                                                                                    Я имею в виду, что, похоже, сама генерация перестановок с этим кодом быстрее, чем генерация перестановок на php другими алгоритмами. Нет сомнений, что на С++ быстрее. Но мне на С и С++ неудобно черновой алгоритмизацией заниматься. Проверю ваш код. Нормальной идеи, как дописать в последовательность промежуточные звенья, пока так и не выпестовал.
                                                                                      0
                                                                                      Понятно. Делайте, конечно, как удобнее. На php можно с php.net/manual/ru/class.spldoublylinkedlist.php поэксперементировать.
                                                                                        0
                                                                                        Я тут подумал.) А зачем факториал высчитывать? Вызывать какую-нибудь функцию рекурсивно да и все. И нет трудоемкого деления вообще и ограничения размера для int на факториал.
                                                                                          0
                                                                                          Наверное, вы правы.
                                                                                          Сделал, последовательность у меня без последней единицы. Для n = 10 получилось 4979527

                                                                                          github.com/dcc0/Superpermutations_php/blob/master/superpermutations.php
                                                                                            0
                                                                                            Да. Вы были правы. Циклический сдвиг не нужен. Он и так получается разрезкой строки и разворотом первой части
                                                                                              0
                                                                                              А будет ли ваше решение работать для чисел больше 9?
                                                                                                0
                                                                                                Да, если использовать алфавит. Или использовать массив, а не строку. Если собирать последовательность, то видимо, нужно писать её в файл или какой-то промежуточный буфер, а потом в файл. Причем с интервалом. Это для больших n. Вообще, я сейчас выкинул все лишнее из кода, получился довольно интересный простенький алгоритм со спиралевидной геометрией. (Наверное, для многих не новость, но я с такой последовательностью не работал) Его, наверное, еще можно улучшить.
                                                                                                <?php
                                                                                                $n = 7;
                                                                                                $fact = 5040;
                                                                                                $perm = "1234567";
                                                                                                for ($i = 1; $i != $fact + 1; $i++)
                                                                                                	{
                                                                                                	print $perm . "\n";
                                                                                                	$mm = $i;
                                                                                                	$m = $n;
                                                                                                	while ($m > 0)
                                                                                                		{
                                                                                                		if ($mm % $m == 0) {
                                                                                                			$mm/= $m--;
                                                                                                			}
                                                                                                		  else
                                                                                                			{
                                                                                                			$perm = substr($perm, $n - $m + 1).strrev(substr($perm, 0, $n - $m + 1));
                                                                                                			continue 2;
                                                                                                			}
                                                                                                		}
                                                                                                	}
                                                                                                ?>
                                                                                                  0
                                                                                                  Я имею ввиду для $perm = «12345678910»;, когда перемещаемое число состоит из нескольких цифр.

                                                                                                  Деление еще можно выкинуть, думаю над этим сейчас.
                                                                                                    0
                                                                                                    Выдаст какой-то результат, но в контексте работы со строками последнее число в строке 12345678910 — это два числа. Достаточно задать значения в массив и будет работать корректно. Только substr надо будет на array_splice переписать и strrev на array_reverse, но разрезку и оборот части строки можно по-другому выразить.
                                                                                                    0
                                                                                                    Готово, не использую факториал и деление. Теперь хоть 100 чисел можно вводить.
                                                                                                      0
                                                                                                      Только, наверное, есть ограничения на длину результатирующей строки. Т.е. при практическом применении нужно периодически сбрасывать строку в файл и очищать переменную, но это уже частный вопрос. Не часть самого алгоритма.
                                                                                                      Про рекурсивный вариант, нашел на Ruby.
                                                                                                      https://rosettacode.org/wiki/Superpermutation_minimisation#Ruby
                                                                                                        0
                                                                                                        Можно просто файловый поток открыть и писать прямо туда.

                                                                                                        На ruby для длины 10 используется одиночный символ 'a' как в шестнадцатеричной системе.

                                                                                                        Не сильно ruby знаю, буду разбираться.
                                                                                                          0
                                                                                                          Я делал так: abсdefghij
                                                                                                          Даже если не использовать массивы, в распоряжении 120 с хвостом символов аски.

                                                                                                          Упорядочил исходный алгоритм на С89 на stdio.
                                                                                                          github.com/dcc0/permutations/blob/master/permutations_spiral.c
                                                                                                            0
                                                                                                            Да, можно и так. Переменная fact только переполняется при большем количестве чисел.

                                                                                                            Для строки, я пробелов наставил между числами и в файл результирующую строку вывожу сейчас.
                                                                                                              0
                                                                                                              Если на строке или массиве возрастающий порядок (а в этом случае это именно так), т.е.
                                                                                                              12345, то последняя перестановка — это реверс от первой. Т.е. 54321. По ней и можно делать остановку.
                                                                                                              т.е. пока ( строка != «54321» ). Но каждый раз сравнивать строки, наверное, не очень хорошо. strcmp вроде бы посимвольно сравнивает. Потеря времени. Вариант с факториалом (субъективно) выглядит более строго в математическом смысле. Такой алгоритм легче понять и перевести на псевдокод или любой язык. Его уже можно воткнуть в курсовую или статью.
                                                                                                                0
                                                                                                                Строка, по сути, это массив символов.

                                                                                                                Да, стравнивать «54321» каждый раз не имеет смысла, точно также как и делимость, тоже не легкая операция по сравнению с простым сравнением больше-меньше.
                                                                                                                Рекурсию не смотрели еще?
                                                                                                                  0
                                                                                                                  Я выводил как-то свой первый алгоритм, там делал именно с проверкой больше меньше: github.com/dcc0/permutations/blob/master/.gitignore/permutations_first_script.c
                                                                                                                  Но там другой порядок вывода, а он не подойдет для создания последовательности. Рекурсивный на Ruby хочу разобрать.
                                                                                                                    0
                                                                                                                    Это вы хитро спрятали файлы.) Обычно .gitignore — это файл в котором записаны файлы которые не учитываются git.

                                                                                                                    Я тут подумал как еще можно оптимизировать. Если строка зеркальная, то почему бы не доходить только до середины, а потом то что получили отзеркалить на вторую половину(считать ничего не нужно) Скорость почти в 2 раза быстрее.

                                                                                                                    Тут еще варианты кода есть
                                                                                                                    github.com/search?q=superpermutation
                                                                                                                      0
                                                                                                                      Я не специально прятал. Вываливал все как есть. Не хотелось вникать, как github устроен.
                                                                                                                      Я тоже думал про то, что считать можно только до половины. Далее пройтись по выводу с конца к началу.
                                                                                                                      Алгоритм на Ruby похоже считает сумму и выводит только часть строки.
                                                                                                                        0
                                                                                                                        Это не про github — это про сам git.

                                                                                                                        Только это будет работать для зеркальной строки, а для более коротких пока паттерн не выявлен.

                                                                                                                        Можно и всю строку вывести если вместо puts вставить:

                                                                                                                        puts n<5 ? ary.join : to_16(ary)

                                                                                0

                                                                                Последовательность 873.


                                                                                Не знаю насколько близко к классике я написал алгоритм который создаёт последовательность 873. Саму её я не нашёл чтобы проверить.


                                                                                Последовательность 873
                                                                                123456123451623451263451236451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654123145623145263145236145231645231465231425631425361425316425314625314265314235614235164235146235142635142365142315642315462315426315423615423165423124563124536124531624531264531246531243561243516243512643512463512436512431562431526431524631524361524316524312564312546312543612543162543126543121345621345261345216345213645213465213425613425163425136425134625134265134215634215364215346215342615342165342135642135462135426135421635421365421324561324516324513624513264513246513241563241536241532641532461532416532413562413526413524613524163524136524132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143256143251643251463251436251432651432156432154632154362154326154321654321

                                                                                В ней 148 последовательностей с повторами(*). И максимально 4 последовательности с повторами подряд. Выглядит симметрично. Просматривается цикличность.


                                                                                2 3 4 6 — Цифрами обозначено сколько идет подряд значений без повторов.
                                                                                * — Каждая звёздочка это последовательность в которой есть повтор минимум одной цифры.


                                                                                6*6*6*6*6**6*6*6*6*6**6*6*6*6*6**6*6*6*6*6***6*6*6*6*6**6*6*6*6*6**6*6*6*6*6**6*6*6*6*6***6*6*6*6*6**6*6*6*6*6**6*6*6*6*6**6*6*6*6*6****6*6*6*6*6**6*6*6*6*6**6*6*6*6*6**6*6*6*6*6***6*6*6*6*6**6*6*6*6*6**6*6*6*6*6**6*6*6*6*6***6*6*6*6*6**6*6*6*6*6**6*6*6*6*6**6*6*6*6*6

                                                                                Последовательность 872.


                                                                                Последовательность 872
                                                                                12345612345162345126345123645132645136245136425136452136451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654132654312645316243516243156243165243162543162453164253146253142653142563142536142531645231465231456231452631452361452316453216453126435126431526431256432156423154623154263154236154231654231564213564215362415362145362154362153462135462134562134652134625134621536421563421653421635421634521634251634215643251643256143256413256431265432165432615342613542613452613425613426513426153246513246531246351246315246312546321546325146325416325461325463124563214563241563245163245613245631246532146532416532461532641532614532615432651436251436521435621435261435216435214635214365124361524361254361245361243561243651423561423516423514623514263514236514326541362541365241356241352641352461352416352413654213654123

                                                                                https://arxiv.org/src/1408.5108v1/anc/superperm-6-866.txt


                                                                                В ней 147 последовательностей с повторами(*). При этом шестёрки разбиты на двойки тройки и четвёрки. Максимально две последовательности с повторами подряд и тех 3 штуки в начале. Похоже на ручное решение головоломки.


                                                                                2 3 4 6 — Цифрами обозначено сколько идет подряд значений без повторов.
                                                                                * — Каждая звёздочка это последовательность в которой есть повтор минимум одной цифры.


                                                                                6*6*6*4*6*6*6*6*2*6**6*6*6*6*6**6*6*6*6*6**6*6*6*6*4*4*3*3*2*6*6*6*6*4*4*6*6*6*6*2*3*6*6*6*6*3*6*3*6*6*4*4*3*6*6*6*6*3*6*2*6*6*6*4*6*6*6*6*2*4*4*6*6*6*6*2*2*6*6*6*2*3*6*2*4*6*6*6*6*2*2*6*4*6*6*4*6*6*6*6*2*3*6*6*6*6*3*2*6*6*4*6*6*4*3*6*4*6*6*6*6*2*4*6*6*6*6*2*2*6*6*6*6*4*3*2*6*4*6*6*6*6*2*6*2
                                                                  –3
                                                                  > Но только для n < 9,8 × 10^42!
                                                                  Ой, камон, да там просто тупо переполнение и всё. Какой-то идиот, писавший софт для Матрицы, решил, что 10^41 хватит всем, а лид прощёлкал.
                                                                    +2

                                                                    Про интегралы Борвейна нашел даже на Хабре:


                                                                    https://m.habr.com/post/146140/


                                                                    А вот про те, что в статье, так и не нагуглилось.

                                                                    –6
                                                                    Лично я не вижу реального применения для операции перестановка в классическом математическом смысле этого действия. Хорошее упражнение для мозгов, но не более.

                                                                    Дело в том что выполнять классическую перестановку для целого числа на Си — не имеет смысла. Оно от этого деградирует!!!
                                                                    Можно и даже иногда нужно выполнять перестановку в двоичном виде. В этом случае целое число перестаёт быть числом, и становится парой структур под объединением — над ними уже можно издеваться без деградации.

                                                                    Если у кого есть примеры использования классической перестановки над десятичными числами в РЕАЛЬНОЙ жизни — то прошу поделиться.
                                                                    Мне интересно!!!
                                                                      0

                                                                      Я как понимаю задача эквивалента какому-то классу задачи коммивояжера. А более важной задачи, полезной в бытовом практическом смысле, наверно и нет

                                                                        –2
                                                                        Вот по этому я и спросил конкретный случай применения!!! Но не эквивалент!!!
                                                                        Потому как в задаче коммивояжера имя объекта не модифицируется.
                                                                        А в классическом варианте перестановки — имя объекта является десятичное число. Само число в видимом десятичном представлении — имя. Как так?

                                                                        И математики на полном серьёзе этим оперируют, что-то складывают и умножают.
                                                                        Я не понимаю смысла — кто сможет мне объяснить!??
                                                                        –2
                                                                        Что и следовало доказать.
                                                                        Простой вопрос, а ответа нету.
                                                                        И кругом одни верующие фанатики.
                                                                          +2
                                                                          Ну вот, например, есть применение перестановок

                                                                          en.wikipedia.org/wiki/Permutation#Applications

                                                                          Или что Вам нужно еще?
                                                                            –1
                                                                            Да, мне нужен пример в котором модифицируется имя объекта перестановки. И обязательно в десятичной системе.
                                                                            Не диапазон имён множества объектов (список), не вариантность состояния в списке, а смену имени объекта перестановки в десятичном представлении.
                                                                            Например вот такая ахинея
                                                                            9=6 потому что количество спичек для составления цифр одинаково
                                                                            123=321 потому что количество цифр одинаково

                                                                            Если объектом перестановки является постоянное статическое имя — его всегда можно идентифицировать, управлять свойствами, добавлять/удалять зависимости, и прочее прочее прочее. Это я и сам умею и с успехом применяю.

                                                                            Но если имя объекта представлено как десятичное многозначное число — начинается полная ахинея, которое я просто не понимаю.
                                                                              0
                                                                              Какое имя объекта? Вы о чем?
                                                                              Десятичная система — это всего лишь форма представления числа.
                                                                              Заверни число в двенадцатеричное представление ничего не изменится.
                                                                              Ну если только умножать на 12, и делимость числа на 2,3,4,6,11,12 проверять в уме.)

                                                                              И действительно, что Вы пишите по-моему не имеет никакого значения. Для чего Вам это нужно? Спички причем? Ну совпадает написание 6 и 9 если их перевернуть и что? Это всего лишь форма записи. Вставь вместо 0...9 — русский алфавит ничего не изменится.
                                                                                –1
                                                                                Какое имя объекта? Вы о чем?

                                                                                Когда число является значением константы или переменной — то всё в норме.
                                                                                Но как только начинаются математические фокусы с перестановкой, то десятичное число превращается в имя. То самое место где оно записано имеет имя в десятичном выражении. Тот самый бред.
                                                                                Я-бы ещё смирился, если-б то самое число считалось адресом. Но математики с умным видом меняют в этом числе цифры местами.!!! И это всё называется классическая перестановка в математике.
                                                                                  0
                                                                                  Я не совсем Вас понимаю. Каким образом, десятичное число превращается в имя по Вашему мнению?
                                                                                  Вы можете больше примеров привести в числовом виде?
                                                                                  У вас проблемы с десятиричной системой?
                                                                                  Попробуйте привести примеры для шестнадцатеричной, ну или любой какой хотите где таких проблем не наблюдается.
                                                                                  Также можете оперировать собачками, кошечками, спичками, если вам так удобнее, математики используют числа.

                                                                                  Вы смирится не можете, я вообще проблемы не наблюдаю.

                                                                                  Судя по тому что Вы написали 9=6.
                                                                                  То можно и 1+1=3 (купи 2 баночки пива 3 получи бесплатно), но это уже не математика — это маркетинг.
                                                                                  Можно и 9=54 (потому что цифру 9 можно составить из 5 спичек, а можно и из 4), что тоже не математика.(для записи)
                                                                                    –1
                                                                                    Вы можете больше примеров привести в числовом виде?

                                                                                    Зачем далеко ходить — вторая картинка темы. Её уже несколько раз повторили, но там она статична.
                                                                                      0

                                                                                      А где вы там видите число? Я там вижу просто набор цифр. Можете 1 2 3 заменить на x y z или на a1 a2 a3 — от этого ничего не поменяется.

                                                                            0
                                                                            Даже последовательности де Брёйна, которые в чём-то схожи с суперперестановками, имеют свои приложения в нейробилогии, робототехнике, для упрощения поиска и брутфорса и т.д.
                                                                            Мы часто даже предположить не можем, какое приложение может иметь какая-то, казалось бы, оторванная от реальности задача.
                                                                            0
                                                                            Фундаментальная наука на то и фундаментальная, что от неё не ждут мгновенного практического применения. Например, теорией чисел занимались несколько тысяч лет без какого-либо практического применения, а сейчас на ней криптография построена.
                                                                            0
                                                                            Можно ещё сократить


                                                                            upd похоже что нет
                                                                              0
                                                                              В последней строке первые три перестановки 123, 231, 313. При этом 123 и 231 встречаются далее. Только 313 не встречается. Значит если сократить первые 2 символа сначала, то мы ничего не потеряем.

                                                                              Ну или я что-то не так понял.
                                                                                0
                                                                                (123)[2(31]{2)(1[3}{2)1]3} — у меня тоже 12 получилось… хм…
                                                                                  +3
                                                                                  У меня вроде 9. Так можно?

                                                                                  123121321
                                                                                  123
                                                                                  231
                                                                                  312
                                                                                  213
                                                                                  132
                                                                                  321
                                                                                    0

                                                                                    Если получается короче и со всеми вариантами то да. Собственно в статье Superpermutation есть этот вариант.


                                                                                    Для четырёх интереснее.

                                                                                      0
                                                                                      Он и в этой статье есть :)
                                                                                      Однако существует и более эффективный способ склейки: 123121321

                                                                                      Я только не понимаю почему народ здесь высчитавать начал без чтения статьи.
                                                                                      Видимо себя проверить.)

                                                                                      Для 4 надо проверить, какая там несостыковка. Хотя наверно лучше для 5 сначала, оно нечетное, возможно четность-нечетность имеет значение.

                                                                                      При n=5, возникает цикл. если следовать старому правилу.

                                                                                      image
                                                                                      image
                                                                                  0
                                                                                  Близко к теме: A portmanteau of every word in English
                                                                                    0
                                                                                    Комментарий был удален
                                                                                      –1
                                                                                      Математика уровня /b.

                                                                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                      Самое читаемое