SLY_G Dec 1 2018 at 10:00

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

7 min

41K

Translation

+60

Comments 77

eyno Dec 1 2018 at 14:23

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

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

KevlarBeaver Dec 1 2018 at 14:36

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

eyno Dec 1 2018 at 15:10

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

vassabi Dec 1 2018 at 15:30

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

UFO just landed and posted this here

vassabi Dec 1 2018 at 19:42

я сам смотрел в таком порядке:
1) читаем новеллу
2) смотрим сериал.

PS: мое личное мнение — лучше в хронологическом.

Aquahawk Dec 1 2018 at 21:22

Как издавался. Сначала первый сезон в том порядке как он выходил, потом второй также как он выходил. Т.к. оригинальная трансляция второго сезона включает первый в порядке внутренней хронологии.

dcc0 Dec 1 2018 at 19:28

Что-то мне подумалось: если задача переходит в задачу коммивояжёра (с ценой), могут ли на практике (при просчете маршрутов) возникать ситуации, когда равнозначных ценовых решений несколько? Статью Эгана нашел с кодом: www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html
Код, кстати, для n 5 генерирует подстроку длиной 154

UFO just landed and posted this here

dcc0 Dec 2 2018 at 15:32

Да. 153. Мне непонятно: при n = 3, n = 4 наблюдается симметрия, т.е. алгоритм доходит до какой-то точки, затем фактически движется обратно — отражение. Я так понял, при n > 6 симметрия пропадает, и это одна из главных проблем.
Кстати, код Эгана и для n = 4 генерирует 34, а должен 33 вроде бы.
Я думал над алгоритмом, как бы я его писал: циклический сдвиг изначальной перестановки до замыкания с записью в файл/буфер, далее проверка последней перестановки, чтобы понять, какое число подставить для продолжения цепочки… да еще и так, чтобы перестановки не повторялись. Трудоемко получается, надо проверять все что было сгенерировано ранее, дабы не словить повторы или не нагенерировать лишнего.
Но что-то мне кажется (только кажется пока), что алгоритм Джонсона Троттера для перестановок тут бы пригодился бы (там как раз циклический сдвиг)… но не уверен.

UFO just landed and posted this here

dcc0 Dec 3 2018 at 10:58

Как я понял, код только длину считает?
Кстати, я не заметил сразу, что
число суперперестановок = факториал числа + число суперперестановок от предыдущего. Т.е. для n = 5 120+33 и т.д. только 872 все ломает

dcc0 Dec 3 2018 at 12:02

(В качестве шутки). Подумалось вчера, какова верхняя граница строки для нормативного словаря русского языка, например, Ожегова. = ) коткатокно — кот, откат, каток, ток, окно, но

UFO just landed and posted this here

dcc0 Dec 3 2018 at 21:09

Класс! Очень компактный код получился и вроде бы довольно понятный.
Всего 120 строк. Начинаю жалеть, что не знаю С++ (и, видимо, ООП, раз там node, struct… Не посмотрел на ваш код и понял, что программист бы из меня не вышел: я бы если написал так, то наверное, неделю сидел, обдумывая)
Интересно, почему у Эгана за 600 строк переваливает.
Форкнул себе.
При n = 7 там симметрия сохраняется.
Интересно, как тот человек сократил до 872 для n 6

vassabi Dec 3 2018 at 21:53

Эган — математик и писатель, а не программист. Ему — можно.

UFO just landed and posted this here

dcc0 Dec 4 2018 at 00:59

Я вникаю в код, пока не все понял. То, что осознал пока: создается структура для n нод, потом от исходной перестановки (если я верно понял) справа налево прокручиваются варианты, то, что в последнем знаке добавляется к общей строке, так до исходной. Не могу понять, когда алгоритм доходит до предела одной ноды, как происходит выбор следующей. Как проверяется, что надо взять следующий фрагмент цепочки не с единицы, а с двойки…
Видимо, мне пока надо его на бумаге еще обдумывать.

UFO just landed and posted this here

dcc0 Dec 4 2018 at 18:24

Огромная благодарность. Более или менее понял. Я со списками не работал никогда, буду знать, чего доучивать.

dcc0 Dec 4 2018 at 13:53

Еще мысли после чтения доказательства:
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.

dcc0 Dec 4 2018 at 19:33

Картинка на всякий случай

UFO just landed and posted this here

dcc0 Dec 6 2018 at 21:39

Вроде бы я понял. Два дня промучился, а всего лишь надо было
посмотреть на картинку.

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

Проверил на n=4, n=5 — все верно.
Тогда, чутье подсказывает, что можно без struct, но пока не на сто процентов уверен.

UFO just landed and posted this here

dcc0 Dec 7 2018 at 01:46

Похоже, что скорость генерации перестановок быстрее. Алгоритм генерации я сделал, но последовательность пока не собрал.
Но можно уже протестировать:
Код
Похоже, и правда быстрее. Если еще оптимизировать. Но там substr и strrev но они довольно быстры в php.

UFO just landed and posted this here

dcc0 Dec 7 2018 at 04:12

Я имею в виду, что, похоже, сама генерация перестановок с этим кодом быстрее, чем генерация перестановок на php другими алгоритмами. Нет сомнений, что на С++ быстрее. Но мне на С и С++ неудобно черновой алгоритмизацией заниматься. Проверю ваш код. Нормальной идеи, как дописать в последовательность промежуточные звенья, пока так и не выпестовал.

UFO just landed and posted this here

dcc0 Dec 7 2018 at 15:53

Наверное, вы правы.
Сделал, последовательность у меня без последней единицы. Для n = 10 получилось 4979527

github.com/dcc0/Superpermutations_php/blob/master/superpermutations.php

dcc0 Dec 7 2018 at 23:05

Да. Вы были правы. Циклический сдвиг не нужен. Он и так получается разрезкой строки и разворотом первой части

UFO just landed and posted this here

dcc0 Dec 8 2018 at 00:08

Да, если использовать алфавит. Или использовать массив, а не строку. Если собирать последовательность, то видимо, нужно писать её в файл или какой-то промежуточный буфер, а потом в файл. Причем с интервалом. Это для больших 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;
			}
		}
	}
?>

UFO just landed and posted this here

dcc0 Dec 8 2018 at 11:19

Выдаст какой-то результат, но в контексте работы со строками последнее число в строке 12345678910 — это два числа. Достаточно задать значения в массив и будет работать корректно. Только substr надо будет на array_splice переписать и strrev на array_reverse, но разрезку и оборот части строки можно по-другому выразить.

UFO just landed and posted this here

dcc0 Dec 8 2018 at 13:26

Только, наверное, есть ограничения на длину результатирующей строки. Т.е. при практическом применении нужно периодически сбрасывать строку в файл и очищать переменную, но это уже частный вопрос. Не часть самого алгоритма.
Про рекурсивный вариант, нашел на Ruby.
https://rosettacode.org/wiki/Superpermutation_minimisation#Ruby

UFO just landed and posted this here

dcc0 Dec 8 2018 at 20:34

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

Упорядочил исходный алгоритм на С89 на stdio.
github.com/dcc0/permutations/blob/master/permutations_spiral.c

UFO just landed and posted this here

dcc0 Dec 8 2018 at 22:53

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

UFO just landed and posted this here

dcc0 Dec 9 2018 at 00:36

Я выводил как-то свой первый алгоритм, там делал именно с проверкой больше меньше: github.com/dcc0/permutations/blob/master/.gitignore/permutations_first_script.c
Но там другой порядок вывода, а он не подойдет для создания последовательности. Рекурсивный на Ruby хочу разобрать.

UFO just landed and posted this here

dcc0 Dec 9 2018 at 11:24

Я не специально прятал. Вываливал все как есть. Не хотелось вникать, как github устроен.
Я тоже думал про то, что считать можно только до половины. Далее пройтись по выводу с конца к началу.
Алгоритм на Ruby похоже считает сумму и выводит только часть строки.

UFO just landed and posted this here

ivan386 Dec 4 2018 at 21:36

Последовательность 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 штуки в начале. Похоже на ручное решение головоломки.

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

dcc0 Dec 4 2018 at 22:19

Ваша последовательность 873 такая же, как по алгоритму MaxVetrov.

UFO just landed and posted this here

ivan386 Dec 4 2018 at 23:31

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

UFO just landed and posted this here

eyno Dec 1 2018 at 22:39

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

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

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

AVI-crak Dec 1 2018 at 22:19

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

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

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

-6

hippohood Dec 1 2018 at 23:00

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

AVI-crak Dec 2 2018 at 00:09

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

И математики на полном серьёзе этим оперируют, что-то складывают и умножают.
Я не понимаю смысла — кто сможет мне объяснить!??

-2

AVI-crak Dec 2 2018 at 06:42

Что и следовало доказать.
Простой вопрос, а ответа нету.
И кругом одни верующие фанатики.

-2

UFO just landed and posted this here

AVI-crak Dec 2 2018 at 18:32

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

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

Но если имя объекта представлено как десятичное многозначное число — начинается полная ахинея, которое я просто не понимаю.

-1

UFO just landed and posted this here

AVI-crak Dec 2 2018 at 21:10

Какое имя объекта? Вы о чем?

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

-1

UFO just landed and posted this here

AVI-crak Dec 3 2018 at 22:00

Вы можете больше примеров привести в числовом виде?

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

-1

mayorovp Dec 4 2018 at 07:12

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

BlazerLuna Dec 7 2018 at 17:09

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

Ktator Dec 2 2018 at 20:12

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

unalacuna Dec 2 2018 at 00:02

Можно ещё сократить

upd похоже что нет

maximw Dec 2 2018 at 00:35

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

Ну или я что-то не так понял.