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

Автор оригинала: Erica Klarreich
  • Перевод

Новое доказательство за авторством австралийского писателя-фантаста Грега Игана и доказательство от 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

    +1
    Для фанатов Харухи решение Игана даёт точную инструкцию о том, как просмотреть все возможные варианты порядка первого сезона, используя всего 93 924 230 411.

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

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

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

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

          PS: мое личное мнение — лучше в хронологическом.
            +1
            Как издавался. Сначала первый сезон в том порядке как он выходил, потом второй также как он выходил. Т.к. оригинальная трансляция второго сезона включает первый в порядке внутренней хронологии.
            0
            Что-то мне подумалось: если задача переходит в задачу коммивояжёра (с ценой), могут ли на практике (при просчете маршрутов) возникать ситуации, когда равнозначных ценовых решений несколько? Статью Эгана нашел с кодом: www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html
            Код, кстати, для n 5 генерирует подстроку длиной 154
            • НЛО прилетело и опубликовало эту надпись здесь
                0
                Да. 153. Мне непонятно: при n = 3, n = 4 наблюдается симметрия, т.е. алгоритм доходит до какой-то точки, затем фактически движется обратно — отражение. Я так понял, при n > 6 симметрия пропадает, и это одна из главных проблем.
                Кстати, код Эгана и для n = 4 генерирует 34, а должен 33 вроде бы.
                Я думал над алгоритмом, как бы я его писал: циклический сдвиг изначальной перестановки до замыкания с записью в файл/буфер, далее проверка последней перестановки, чтобы понять, какое число подставить для продолжения цепочки… да еще и так, чтобы перестановки не повторялись. Трудоемко получается, надо проверять все что было сгенерировано ранее, дабы не словить повторы или не нагенерировать лишнего.
                Но что-то мне кажется (только кажется пока), что алгоритм Джонсона Троттера для перестановок тут бы пригодился бы (там как раз циклический сдвиг)… но не уверен.
                • НЛО прилетело и опубликовало эту надпись здесь
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      Как я понял, код только длину считает?
                      Кстати, я не заметил сразу, что
                      число суперперестановок = факториал числа + число суперперестановок от предыдущего. Т.е. для n = 5 120+33 и т.д. только 872 все ломает
                        0
                        (В качестве шутки). Подумалось вчера, какова верхняя граница строки для нормативного словаря русского языка, например, Ожегова. = ) коткатокно — кот, откат, каток, ток, окно, но
                        • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            Класс! Очень компактный код получился и вроде бы довольно понятный.
                            Всего 120 строк. Начинаю жалеть, что не знаю С++ (и, видимо, ООП, раз там node, struct… Не посмотрел на ваш код и понял, что программист бы из меня не вышел: я бы если написал так, то наверное, неделю сидел, обдумывая)
                            Интересно, почему у Эгана за 600 строк переваливает.
                            Форкнул себе.
                            При n = 7 там симметрия сохраняется.
                            Интересно, как тот человек сократил до 872 для n 6
                              0
                              Эган — математик и писатель, а не программист. Ему — можно.
                              • НЛО прилетело и опубликовало эту надпись здесь
                                  0
                                  Я вникаю в код, пока не все понял. То, что осознал пока: создается структура для n нод, потом от исходной перестановки (если я верно понял) справа налево прокручиваются варианты, то, что в последнем знаке добавляется к общей строке, так до исходной. Не могу понять, когда алгоритм доходит до предела одной ноды, как происходит выбор следующей. Как проверяется, что надо взять следующий фрагмент цепочки не с единицы, а с двойки…
                                  Видимо, мне пока надо его на бумаге еще обдумывать.
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                      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
                                          Вроде бы я понял. Два дня промучился, а всего лишь надо было
                                          посмотреть на картинку.

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

                                          Проверил на n=4, n=5 — все верно.
                                          Тогда, чутье подсказывает, что можно без struct, но пока не на сто процентов уверен.
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                              0
                                              Похоже, что скорость генерации перестановок быстрее. Алгоритм генерации я сделал, но последовательность пока не собрал.
                                              Но можно уже протестировать:
                                              Код
                                              Похоже, и правда быстрее. Если еще оптимизировать. Но там substr и strrev но они довольно быстры в php.
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                  0
                                                  Я имею в виду, что, похоже, сама генерация перестановок с этим кодом быстрее, чем генерация перестановок на php другими алгоритмами. Нет сомнений, что на С++ быстрее. Но мне на С и С++ неудобно черновой алгоритмизацией заниматься. Проверю ваш код. Нормальной идеи, как дописать в последовательность промежуточные звенья, пока так и не выпестовал.
                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                        0
                                                        Наверное, вы правы.
                                                        Сделал, последовательность у меня без последней единицы. Для n = 10 получилось 4979527

                                                        github.com/dcc0/Superpermutations_php/blob/master/superpermutations.php
                                                          0
                                                          Да. Вы были правы. Циклический сдвиг не нужен. Он и так получается разрезкой строки и разворотом первой части
                                                          • НЛО прилетело и опубликовало эту надпись здесь
                                                              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
                                                                  Выдаст какой-то результат, но в контексте работы со строками последнее число в строке 12345678910 — это два числа. Достаточно задать значения в массив и будет работать корректно. Только substr надо будет на array_splice переписать и strrev на array_reverse, но разрезку и оборот части строки можно по-другому выразить.
                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                    0
                                                                    Только, наверное, есть ограничения на длину результатирующей строки. Т.е. при практическом применении нужно периодически сбрасывать строку в файл и очищать переменную, но это уже частный вопрос. Не часть самого алгоритма.
                                                                    Про рекурсивный вариант, нашел на Ruby.
                                                                    https://rosettacode.org/wiki/Superpermutation_minimisation#Ruby
                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                        0
                                                                        Я делал так: abсdefghij
                                                                        Даже если не использовать массивы, в распоряжении 120 с хвостом символов аски.

                                                                        Упорядочил исходный алгоритм на С89 на stdio.
                                                                        github.com/dcc0/permutations/blob/master/permutations_spiral.c
                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                            0
                                                                            Если на строке или массиве возрастающий порядок (а в этом случае это именно так), т.е.
                                                                            12345, то последняя перестановка — это реверс от первой. Т.е. 54321. По ней и можно делать остановку.
                                                                            т.е. пока ( строка != «54321» ). Но каждый раз сравнивать строки, наверное, не очень хорошо. strcmp вроде бы посимвольно сравнивает. Потеря времени. Вариант с факториалом (субъективно) выглядит более строго в математическом смысле. Такой алгоритм легче понять и перевести на псевдокод или любой язык. Его уже можно воткнуть в курсовую или статью.
                                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                                                0
                                                                                Я выводил как-то свой первый алгоритм, там делал именно с проверкой больше меньше: github.com/dcc0/permutations/blob/master/.gitignore/permutations_first_script.c
                                                                                Но там другой порядок вывода, а он не подойдет для создания последовательности. Рекурсивный на Ruby хочу разобрать.
                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                    0
                                                                                    Я не специально прятал. Вываливал все как есть. Не хотелось вникать, как github устроен.
                                                                                    Я тоже думал про то, что считать можно только до половины. Далее пройтись по выводу с конца к началу.
                                                                                    Алгоритм на Ruby похоже считает сумму и выводит только часть строки.
                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                              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
                                                +1
                                                Ваша последовательность 873 такая же, как по алгоритму MaxVetrov.
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                    0

                                                    Спасибо. Вроде всё по классике.

                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                      +2

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


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


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

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

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

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

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

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

                                          И математики на полном серьёзе этим оперируют, что-то складывают и умножают.
                                          Я не понимаю смысла — кто сможет мне объяснить!??
                                          –2
                                          Что и следовало доказать.
                                          Простой вопрос, а ответа нету.
                                          И кругом одни верующие фанатики.
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                              –1
                                              Да, мне нужен пример в котором модифицируется имя объекта перестановки. И обязательно в десятичной системе.
                                              Не диапазон имён множества объектов (список), не вариантность состояния в списке, а смену имени объекта перестановки в десятичном представлении.
                                              Например вот такая ахинея
                                              9=6 потому что количество спичек для составления цифр одинаково
                                              123=321 потому что количество цифр одинаково

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

                                              Но если имя объекта представлено как десятичное многозначное число — начинается полная ахинея, которое я просто не понимаю.
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                  –1
                                                  Какое имя объекта? Вы о чем?

                                                  Когда число является значением константы или переменной — то всё в норме.
                                                  Но как только начинаются математические фокусы с перестановкой, то десятичное число превращается в имя. То самое место где оно записано имеет имя в десятичном выражении. Тот самый бред.
                                                  Я-бы ещё смирился, если-б то самое число считалось адресом. Но математики с умным видом меняют в этом числе цифры местами.!!! И это всё называется классическая перестановка в математике.
                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                      –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 получилось… хм…
                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                      0

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


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

                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                    0
                                                    Близко к теме: A portmanteau of every word in English
                                                      0
                                                      Комментарий был удален
                                                        –1
                                                        Математика уровня /b.

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

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