Комментарии 77
Для фанатов Харухи решение Игана даёт точную инструкцию о том, как просмотреть все возможные варианты порядка первого сезона, используя всего 93 924 230 411.
Так я не понял, решение дает конкретную суперперестановку или все-таки количество ее элементов?
Я тоже не понял. В статье написано, что уже можно брать готовую перестановку и смотреть все серии. Но при этом приводятся формулы, с помощью которых пожно вычилисть только количество элементов для нижней и верхней границы.
насколько я понял — это не решение суперперестановки, а оценка решения сверху (т.е. настоящее решение может быть равно ему или быть короче).
При этом оно позволяет вычислить суперперестановку для этого количества элементов (если вы вдруг захотите начать их смотреть — у Игана есть описание алгоритма и даже код на С написан для генерирования).
При этом оно позволяет вычислить суперперестановку для этого количества элементов (если вы вдруг захотите начать их смотреть — у Игана есть описание алгоритма и даже код на С написан для генерирования).
НЛО прилетело и опубликовало эту надпись здесь
я сам смотрел в таком порядке:
1) читаем новеллу
2) смотрим сериал.
PS: мое личное мнение — лучше в хронологическом.
1) читаем новеллу
2) смотрим сериал.
PS: мое личное мнение — лучше в хронологическом.
Как издавался. Сначала первый сезон в том порядке как он выходил, потом второй также как он выходил. Т.к. оригинальная трансляция второго сезона включает первый в порядке внутренней хронологии.
Что-то мне подумалось: если задача переходит в задачу коммивояжёра (с ценой), могут ли на практике (при просчете маршрутов) возникать ситуации, когда равнозначных ценовых решений несколько? Статью Эгана нашел с кодом: www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html
Код, кстати, для n 5 генерирует подстроку длиной 154
Код, кстати, для n 5 генерирует подстроку длиной 154
НЛО прилетело и опубликовало эту надпись здесь
Да. 153. Мне непонятно: при n = 3, n = 4 наблюдается симметрия, т.е. алгоритм доходит до какой-то точки, затем фактически движется обратно — отражение. Я так понял, при n > 6 симметрия пропадает, и это одна из главных проблем.
Кстати, код Эгана и для n = 4 генерирует 34, а должен 33 вроде бы.
Я думал над алгоритмом, как бы я его писал: циклический сдвиг изначальной перестановки до замыкания с записью в файл/буфер, далее проверка последней перестановки, чтобы понять, какое число подставить для продолжения цепочки… да еще и так, чтобы перестановки не повторялись. Трудоемко получается, надо проверять все что было сгенерировано ранее, дабы не словить повторы или не нагенерировать лишнего.
Но что-то мне кажется (только кажется пока), что алгоритм Джонсона Троттера для перестановок тут бы пригодился бы (там как раз циклический сдвиг)… но не уверен.
Кстати, код Эгана и для n = 4 генерирует 34, а должен 33 вроде бы.
Я думал над алгоритмом, как бы я его писал: циклический сдвиг изначальной перестановки до замыкания с записью в файл/буфер, далее проверка последней перестановки, чтобы понять, какое число подставить для продолжения цепочки… да еще и так, чтобы перестановки не повторялись. Трудоемко получается, надо проверять все что было сгенерировано ранее, дабы не словить повторы или не нагенерировать лишнего.
Но что-то мне кажется (только кажется пока), что алгоритм Джонсона Троттера для перестановок тут бы пригодился бы (там как раз циклический сдвиг)… но не уверен.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Как я понял, код только длину считает?
Кстати, я не заметил сразу, что
число суперперестановок = факториал числа + число суперперестановок от предыдущего. Т.е. для n = 5 120+33 и т.д. только 872 все ломает
Кстати, я не заметил сразу, что
число суперперестановок = факториал числа + число суперперестановок от предыдущего. Т.е. для n = 5 120+33 и т.д. только 872 все ломает
(В качестве шутки). Подумалось вчера, какова верхняя граница строки для нормативного словаря русского языка, например, Ожегова. = ) коткатокно — кот, откат, каток, ток, окно, но
НЛО прилетело и опубликовало эту надпись здесь
Класс! Очень компактный код получился и вроде бы довольно понятный.
Всего 120 строк. Начинаю жалеть, что не знаю С++ (и, видимо, ООП, раз там node, struct… Не посмотрел на ваш код и понял, что программист бы из меня не вышел: я бы если написал так, то наверное, неделю сидел, обдумывая)
Интересно, почему у Эгана за 600 строк переваливает.
Форкнул себе.
При n = 7 там симметрия сохраняется.
Интересно, как тот человек сократил до 872 для n 6
Всего 120 строк. Начинаю жалеть, что не знаю С++ (и, видимо, ООП, раз там node, struct… Не посмотрел на ваш код и понял, что программист бы из меня не вышел: я бы если написал так, то наверное, неделю сидел, обдумывая)
Интересно, почему у Эгана за 600 строк переваливает.
Форкнул себе.
При n = 7 там симметрия сохраняется.
Интересно, как тот человек сократил до 872 для n 6
Эган — математик и писатель, а не программист. Ему — можно.
НЛО прилетело и опубликовало эту надпись здесь
Я вникаю в код, пока не все понял. То, что осознал пока: создается структура для n нод, потом от исходной перестановки (если я верно понял) справа налево прокручиваются варианты, то, что в последнем знаке добавляется к общей строке, так до исходной. Не могу понять, когда алгоритм доходит до предела одной ноды, как происходит выбор следующей. Как проверяется, что надо взять следующий фрагмент цепочки не с единицы, а с двойки…
Видимо, мне пока надо его на бумаге еще обдумывать.
Видимо, мне пока надо его на бумаге еще обдумывать.
Еще мысли после чтения доказательства:
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.
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.
НЛО прилетело и опубликовало эту надпись здесь
Вроде бы я понял. Два дня промучился, а всего лишь надо было
посмотреть на картинку.
Тогда на мой взгляд алгоритм такой (если не напутал):
1) Крутим до n, например n = 3
123
231
312
2) Проверяем делится ли номер итерации нацело на n (вроде также как в написанном коде у MaxVetrov и Эгана)
Делится, тогда идем по хвосту слева направо (два прохода, чтобы снова не делилось нацело )
3) То, что осталось — идет в начало, перевернутый хвост идет в конец.
4) Снова крутим.
213
132
321
5) Дошли до факториала. Остановка.
Проверил на n=4, n=5 — все верно.
Тогда, чутье подсказывает, что можно без struct, но пока не на сто процентов уверен.
посмотреть на картинку.
Тогда на мой взгляд алгоритм такой (если не напутал):
1) Крутим до n, например n = 3
123
231
312
2) Проверяем делится ли номер итерации нацело на n (вроде также как в написанном коде у MaxVetrov и Эгана)
Делится, тогда идем по хвосту слева направо (два прохода, чтобы снова не делилось нацело )
3) То, что осталось — идет в начало, перевернутый хвост идет в конец.
4) Снова крутим.
213
132
321
5) Дошли до факториала. Остановка.
Проверил на n=4, n=5 — все верно.
Тогда, чутье подсказывает, что можно без struct, но пока не на сто процентов уверен.
НЛО прилетело и опубликовало эту надпись здесь
Похоже, что скорость генерации перестановок быстрее. Алгоритм генерации я сделал, но последовательность пока не собрал.
Но можно уже протестировать:
Код
Похоже, и правда быстрее. Если еще оптимизировать. Но там substr и strrev но они довольно быстры в php.
Но можно уже протестировать:
Код
Похоже, и правда быстрее. Если еще оптимизировать. Но там substr и strrev но они довольно быстры в php.
НЛО прилетело и опубликовало эту надпись здесь
Я имею в виду, что, похоже, сама генерация перестановок с этим кодом быстрее, чем генерация перестановок на php другими алгоритмами. Нет сомнений, что на С++ быстрее. Но мне на С и С++ неудобно черновой алгоритмизацией заниматься. Проверю ваш код. Нормальной идеи, как дописать в последовательность промежуточные звенья, пока так и не выпестовал.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Наверное, вы правы.
Сделал, последовательность у меня без последней единицы. Для n = 10 получилось 4979527
github.com/dcc0/Superpermutations_php/blob/master/superpermutations.php
Сделал, последовательность у меня без последней единицы. Для n = 10 получилось 4979527
github.com/dcc0/Superpermutations_php/blob/master/superpermutations.php
Да. Вы были правы. Циклический сдвиг не нужен. Он и так получается разрезкой строки и разворотом первой части
НЛО прилетело и опубликовало эту надпись здесь
Да, если использовать алфавит. Или использовать массив, а не строку. Если собирать последовательность, то видимо, нужно писать её в файл или какой-то промежуточный буфер, а потом в файл. Причем с интервалом. Это для больших 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;
}
}
}
?>НЛО прилетело и опубликовало эту надпись здесь
Выдаст какой-то результат, но в контексте работы со строками последнее число в строке 12345678910 — это два числа. Достаточно задать значения в массив и будет работать корректно. Только substr надо будет на array_splice переписать и strrev на array_reverse, но разрезку и оборот части строки можно по-другому выразить.
НЛО прилетело и опубликовало эту надпись здесь
Только, наверное, есть ограничения на длину результатирующей строки. Т.е. при практическом применении нужно периодически сбрасывать строку в файл и очищать переменную, но это уже частный вопрос. Не часть самого алгоритма.
Про рекурсивный вариант, нашел на Ruby.
https://rosettacode.org/wiki/Superpermutation_minimisation#Ruby
Про рекурсивный вариант, нашел на Ruby.
https://rosettacode.org/wiki/Superpermutation_minimisation#Ruby
НЛО прилетело и опубликовало эту надпись здесь
Я делал так: abсdefghij
Даже если не использовать массивы, в распоряжении 120 с хвостом символов аски.
Упорядочил исходный алгоритм на С89 на stdio.
github.com/dcc0/permutations/blob/master/permutations_spiral.c
Даже если не использовать массивы, в распоряжении 120 с хвостом символов аски.
Упорядочил исходный алгоритм на С89 на stdio.
github.com/dcc0/permutations/blob/master/permutations_spiral.c
НЛО прилетело и опубликовало эту надпись здесь
Если на строке или массиве возрастающий порядок (а в этом случае это именно так), т.е.
12345, то последняя перестановка — это реверс от первой. Т.е. 54321. По ней и можно делать остановку.
т.е. пока ( строка != «54321» ). Но каждый раз сравнивать строки, наверное, не очень хорошо. strcmp вроде бы посимвольно сравнивает. Потеря времени. Вариант с факториалом (субъективно) выглядит более строго в математическом смысле. Такой алгоритм легче понять и перевести на псевдокод или любой язык. Его уже можно воткнуть в курсовую или статью.
12345, то последняя перестановка — это реверс от первой. Т.е. 54321. По ней и можно делать остановку.
т.е. пока ( строка != «54321» ). Но каждый раз сравнивать строки, наверное, не очень хорошо. strcmp вроде бы посимвольно сравнивает. Потеря времени. Вариант с факториалом (субъективно) выглядит более строго в математическом смысле. Такой алгоритм легче понять и перевести на псевдокод или любой язык. Его уже можно воткнуть в курсовую или статью.
НЛО прилетело и опубликовало эту надпись здесь
Я выводил как-то свой первый алгоритм, там делал именно с проверкой больше меньше: github.com/dcc0/permutations/blob/master/.gitignore/permutations_first_script.c
Но там другой порядок вывода, а он не подойдет для создания последовательности. Рекурсивный на Ruby хочу разобрать.
Но там другой порядок вывода, а он не подойдет для создания последовательности. Рекурсивный на Ruby хочу разобрать.
НЛО прилетело и опубликовало эту надпись здесь
Последовательность 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В ней 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НЛО прилетело и опубликовало эту надпись здесь
Про интегралы Борвейна нашел даже на Хабре:
https://m.habr.com/post/146140/
А вот про те, что в статье, так и не нагуглилось.
Лично я не вижу реального применения для операции перестановка в классическом математическом смысле этого действия. Хорошее упражнение для мозгов, но не более.
Дело в том что выполнять классическую перестановку для целого числа на Си — не имеет смысла. Оно от этого деградирует!!!
Можно и даже иногда нужно выполнять перестановку в двоичном виде. В этом случае целое число перестаёт быть числом, и становится парой структур под объединением — над ними уже можно издеваться без деградации.
Если у кого есть примеры использования классической перестановки над десятичными числами в РЕАЛЬНОЙ жизни — то прошу поделиться.
Мне интересно!!!
Дело в том что выполнять классическую перестановку для целого числа на Си — не имеет смысла. Оно от этого деградирует!!!
Можно и даже иногда нужно выполнять перестановку в двоичном виде. В этом случае целое число перестаёт быть числом, и становится парой структур под объединением — над ними уже можно издеваться без деградации.
Если у кого есть примеры использования классической перестановки над десятичными числами в РЕАЛЬНОЙ жизни — то прошу поделиться.
Мне интересно!!!
Я как понимаю задача эквивалента какому-то классу задачи коммивояжера. А более важной задачи, полезной в бытовом практическом смысле, наверно и нет
Вот по этому я и спросил конкретный случай применения!!! Но не эквивалент!!!
Потому как в задаче коммивояжера имя объекта не модифицируется.
А в классическом варианте перестановки — имя объекта является десятичное число. Само число в видимом десятичном представлении — имя. Как так?
И математики на полном серьёзе этим оперируют, что-то складывают и умножают.
Я не понимаю смысла — кто сможет мне объяснить!??
Потому как в задаче коммивояжера имя объекта не модифицируется.
А в классическом варианте перестановки — имя объекта является десятичное число. Само число в видимом десятичном представлении — имя. Как так?
И математики на полном серьёзе этим оперируют, что-то складывают и умножают.
Я не понимаю смысла — кто сможет мне объяснить!??
Что и следовало доказать.
Простой вопрос, а ответа нету.
И кругом одни верующие фанатики.
Простой вопрос, а ответа нету.
И кругом одни верующие фанатики.
НЛО прилетело и опубликовало эту надпись здесь
Да, мне нужен пример в котором модифицируется имя объекта перестановки. И обязательно в десятичной системе.
Не диапазон имён множества объектов (список), не вариантность состояния в списке, а смену имени объекта перестановки в десятичном представлении.
Например вот такая ахинея
9=6 потому что количество спичек для составления цифр одинаково
123=321 потому что количество цифр одинаково
Если объектом перестановки является постоянное статическое имя — его всегда можно идентифицировать, управлять свойствами, добавлять/удалять зависимости, и прочее прочее прочее. Это я и сам умею и с успехом применяю.
Но если имя объекта представлено как десятичное многозначное число — начинается полная ахинея, которое я просто не понимаю.
Не диапазон имён множества объектов (список), не вариантность состояния в списке, а смену имени объекта перестановки в десятичном представлении.
Например вот такая ахинея
9=6 потому что количество спичек для составления цифр одинаково
123=321 потому что количество цифр одинаково
Если объектом перестановки является постоянное статическое имя — его всегда можно идентифицировать, управлять свойствами, добавлять/удалять зависимости, и прочее прочее прочее. Это я и сам умею и с успехом применяю.
Но если имя объекта представлено как десятичное многозначное число — начинается полная ахинея, которое я просто не понимаю.
НЛО прилетело и опубликовало эту надпись здесь
Какое имя объекта? Вы о чем?
Когда число является значением константы или переменной — то всё в норме.
Но как только начинаются математические фокусы с перестановкой, то десятичное число превращается в имя. То самое место где оно записано имеет имя в десятичном выражении. Тот самый бред.
Я-бы ещё смирился, если-б то самое число считалось адресом. Но математики с умным видом меняют в этом числе цифры местами.!!! И это всё называется классическая перестановка в математике.
Даже последовательности де Брёйна, которые в чём-то схожи с суперперестановками, имеют свои приложения в нейробилогии, робототехнике, для упрощения поиска и брутфорса и т.д.
Мы часто даже предположить не можем, какое приложение может иметь какая-то, казалось бы, оторванная от реальности задача.
Мы часто даже предположить не можем, какое приложение может иметь какая-то, казалось бы, оторванная от реальности задача.
Фундаментальная наука на то и фундаментальная, что от неё не ждут мгновенного практического применения. Например, теорией чисел занимались несколько тысяч лет без какого-либо практического применения, а сейчас на ней криптография построена.
Можно ещё сократить
upd похоже что нет
upd похоже что нет
В последней строке первые три перестановки 123, 231, 313. При этом 123 и 231 встречаются далее. Только 313 не встречается. Значит если сократить первые 2 символа сначала, то мы ничего не потеряем.
Ну или я что-то не так понял.
Ну или я что-то не так понял.
(123)[2(31]{2)(1[3}{2)1]3} — у меня тоже 12 получилось… хм…
НЛО прилетело и опубликовало эту надпись здесь
Если получается короче и со всеми вариантами то да. Собственно в статье Superpermutation есть этот вариант.
Для четырёх интереснее.
Близко к теме: A portmanteau of every word in English
Комментарий был удален
Математика уровня /b.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Загадочный математический гений и писатель продвигают решение задачи о перестановке