Новое доказательство за авторством австралийского писателя-фантаста Грега Игана и доказательство от 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 млн эпизодов – однако, этого достаточно, чтобы начать готовиться ко второму сезону.
valdemartorch
Даже теология привносит больше пользы чем математика.
vassabi
я у вас опечатку поправил, можете не благодарить.
Понятно, что у вас — так, но в жизни множество вещей, профессий и отраслей, где без математики — вообще никак.
serg_deep
Ctacfs
Ваша правда. Ни один запуск ракеты не обходится без освящения.
KevlarBeaver
Вроде, это только наша национальная традиция. Поправьте, если ошибаюсь.
Хьюстон, у нас проблемы, взлёт откладывается, кадило забыли!
ihouser
А я завидую математикам черной завистью — они решают такие увлекательные задачи. Вот бы мне быть хоть на 10% таким же умным.
KevlarBeaver
У нас тебе кушать было б нечего, будь ты математиком. А программистом можно на жизнь хоть как-то зарабатывать.
RussDragon
Никто не мешает совмещать :)
0xd34df00d
Мешает ограниченность времени и ментальных ресурсов.
RussDragon
Ну, смотря как к этому подходить. При некотором уровне абстракции программирование – математика и многое из математики применимо в программировании (и наоборот).
Я бы даже сказал, что IT как раз та сфера, где совмещать математику и инженерию проще всего.
old_bear
Стухла молодёжь совсем. Никакой тонкости и изящества, одна толстота.
Печаль.
tchspprt
Тащемта он больше похож на откато-распильного кремлебота по заказу «надо молодежи полезные комментарии в тырнеты пописать о разрухе в айти-сфере, глядишь заводы заполним, чего там айтишное есть в стране, TM?», чем на саму молодежь. Поанализируйте другие его комменты — настолько отвратительно толсто быть не может совсем.
Ctacfs
> настолько отвратительно толсто быть не может совсем.
Недавно в интернете?
tchspprt
Давненько уже.
Профит от троллинга на сайте с троллингоустойчивой ЦА нулевой. Любой школьник это осознает. Да и выборка странная КМК — тролли обычно идут в места понажористей, у него из таковых только коммент в пост одного российского поисковика с содержанием сравнения с одним нероссийским. И это после событий с попыткой
честногоприобретения этого самого российского поисковика российским банком.А вот комменты с содержанием «снова облажались макдонольдсовые» — неплохой маячок.
KevlarBeaver
Интересно, кто ему инвайт дал...
tchspprt
Давно уже без инвайта можно регаться. Как минимум тогда, когда зарегался я — дату можете в профиле увидеть.
С подключеньицем.
Ctacfs
Профита от любого троллинга нет никакого, это шутка, над которой смеется пошутивший, а не услышавший.
KevlarBeaver
Как одной фразой слить себя на техническом ресурсе…
ilitaexperta
Хабр относится к техническим ресурсам примерно как техническая вода к питьевой
KevlarBeaver
Ну какой есть. По-моему, один из лучших, если не лучший, на просторах рунета.
Shadow_Man
Он перестал таким быть, как только открыли инвайт для всех.
RussDragon
Он перестал таким быть, как только токсичность коммьюинити начала выгонять скромных и ранимых инженеров и программистов с сайта :)
Хотя, конечно, не исключено и влияние инвайтов для всех.
Keyten
8-10 лет назад?
RussDragon
Ну где-то так, да :)
jorgen_steinbach
Интересно, возможно ли создать сайт для скромных и ранимых инженеров и программистов, такой, чтобы у тролей вообще не было возможности прийти туда и их выгнать.
RussDragon
Ну, Хабр можно было бы еще спасти, измени они систему хабракармы. Чтобы не было задавливание альтернативного мнения ограничениями на сайте.
(имхо)
Но это совсем оффтопик и предлагаю все же вернуться к статье.
vsb
Для меня HN стал таким сайтом. Не знаю, как им это удаётся, но я чувствую себя там комфортно в отличие от хабра, на котором я даже писать могу то ли раз в сутки, то ли около того.
Anshi85
Дайте пожалуйста ссылочку в личку, а то я тут недавно высказал свое мнение по поводу Линукса и вирусов и меня заминусили, хотя никого и не обижал и не троллил. Иногда кажется что хабр населен задротами — неудачниками, которые стараются за счёт минусов самоутвердиться.
vsb
news.ycombinator.com
AVI-crak
Угу, пришёл напиться, а там уже ноги помыли.
По этому всегда читаю шапку комментариев, до мутной воды.
Am0ralist
Не правда. Он к этому 19 комментариев шёл!
kekekeks
Есть подозрение, что комментатор имел ввиду теологические вопросы Харухизма, которые и привели к появлению гипотезы о нижней границе.
Но был не понят неискушённой в альтернативных религиозных веяниях аудиторией.
arielf
Вау! Главные качества нашего инженера:
hippohood
Порядок в списке качеств по убыванию значимости?)
<шутка про приоритеты>
arielf
Угу, главное — вера, а прочее можно и измениь лёгким росчерком пера ;-)
tvr
О, мифический притесняемый WASP нашёлся?
MaxVetrov
Какой-то странный Вы программист.
Я сомневаюсь, что Вам математика никогда не пригождалась как программисту.
Не нравится — не пишите, у всех вкусы разные.
lain8dono
Замечу, что для многих задач действительно достаточно арифметики уровня начальных классов.
MaxVetrov
Да, есть либы которые все решают.
По поводу математики для программистов уже статья была.
habr.com/company/yandex/blog/239339
Понятно, что не вся математика нужна, а какие то определенные области, и все зависит от выполняемой задачи.
Не нужно знать всё, нужно свободно ориентироваться и усвоить что-то новое когда понадобится.
Тут комбинаторика — и я считаю, что каждому хорошему программисту это полезно.
sotnikdv
Я прекрасно живу без религиозных мозговых слизней. И отлично буду жить, если все религиозные люди вместе с «пропагандитами» их религий покинут планету прямо немедленно в сию же секунду (улетят в прекрасное будущее, в рай и т.д.). Скорее всего, даже гораздо лучше.
А вот если исчезнут математики, учителя математики и математика, как наука, то жить мы будем где-то между первобытно общинным строем и первыми поселениями из веток и досок. Минус вся физика-химия-медицина-строительство-айти и много-много чего еще.
P.S. И храмы ваши все тоже придется разобрать, там математики и геометрии при строительстве просто дофига. И пирамиды придется раскатать. Вручную.
P.P.S. Но спасибо вам за то, что еще раз показали, почему религию столь яростно демонтировали в 1917 году. Во-первых власть, во-вторых яростная религиозность обратно коррелирует с интеллектом и общим развитием страны.
BD9
В 1917 году уничтожали одну религиозную систему, заменяя другой, сейчас они сливаются вместе т.к. близкородственны.
aleaksah
tvr
Это Чумак заряжал, а Кашпировский рассасывал и затягивал.
Ну нельзя же так путать эпохальные прорывные технологии в телемедицине.
eyno
Так я не понял, решение дает конкретную суперперестановку или все-таки количество ее элементов?
KevlarBeaver
Я тоже не понял. В статье написано, что уже можно брать готовую перестановку и смотреть все серии. Но при этом приводятся формулы, с помощью которых пожно вычилисть только количество элементов для нижней и верхней границы.
eyno
Расходимся, нас на… обманули. ©
vassabi
насколько я понял — это не решение суперперестановки, а оценка решения сверху (т.е. настоящее решение может быть равно ему или быть короче).
При этом оно позволяет вычислить суперперестановку для этого количества элементов (если вы вдруг захотите начать их смотреть — у Игана есть описание алгоритма и даже код на С написан для генерирования).
KonkovVladimir
Так все таки стоит смотреть сериал и в каком прядке?
vassabi
я сам смотрел в таком порядке:
1) читаем новеллу
2) смотрим сериал.
PS: мое личное мнение — лучше в хронологическом.
Aquahawk
Как издавался. Сначала первый сезон в том порядке как он выходил, потом второй также как он выходил. Т.к. оригинальная трансляция второго сезона включает первый в порядке внутренней хронологии.
dcc0
Что-то мне подумалось: если задача переходит в задачу коммивояжёра (с ценой), могут ли на практике (при просчете маршрутов) возникать ситуации, когда равнозначных ценовых решений несколько? Статью Эгана нашел с кодом: www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html
Код, кстати, для n 5 генерирует подстроку длиной 154
MaxVetrov
153 должен.
en.wikipedia.org/wiki/Superpermutation
dcc0
Да. 153. Мне непонятно: при n = 3, n = 4 наблюдается симметрия, т.е. алгоритм доходит до какой-то точки, затем фактически движется обратно — отражение. Я так понял, при n > 6 симметрия пропадает, и это одна из главных проблем.
Кстати, код Эгана и для n = 4 генерирует 34, а должен 33 вроде бы.
Я думал над алгоритмом, как бы я его писал: циклический сдвиг изначальной перестановки до замыкания с записью в файл/буфер, далее проверка последней перестановки, чтобы понять, какое число подставить для продолжения цепочки… да еще и так, чтобы перестановки не повторялись. Трудоемко получается, надо проверять все что было сгенерировано ранее, дабы не словить повторы или не нагенерировать лишнего.
Но что-то мне кажется (только кажется пока), что алгоритм Джонсона Троттера для перестановок тут бы пригодился бы (там как раз циклический сдвиг)… но не уверен.
MaxVetrov
для n=4
1234123142134214324132431243214231 — код Эгана
1234123142_31243121342132413214321 — oeis.org/A180632
Может Эган ошибку где-то совершил. ("_" вставил для удобства просмотра, пробел не помогает)
MaxVetrov
Написал незамысловатый код на С++, длина совпадает:
github.com/tigertv/superpermutation
dcc0
Как я понял, код только длину считает?
Кстати, я не заметил сразу, что
число суперперестановок = факториал числа + число суперперестановок от предыдущего. Т.е. для n = 5 120+33 и т.д. только 872 все ломает
dcc0
(В качестве шутки). Подумалось вчера, какова верхняя граница строки для нормативного словаря русского языка, например, Ожегова. = ) коткатокно — кот, откат, каток, ток, окно, но
MaxVetrov
Я тоже не заметил.)
Ну тут вообще вариантов целая куча, учитывая, что длина слов разная, и еще отсекать нужно неправильные наборы cлов.
dcc0
Класс! Очень компактный код получился и вроде бы довольно понятный.
Всего 120 строк. Начинаю жалеть, что не знаю С++ (и, видимо, ООП, раз там node, struct… Не посмотрел на ваш код и понял, что программист бы из меня не вышел: я бы если написал так, то наверное, неделю сидел, обдумывая)
Интересно, почему у Эгана за 600 строк переваливает.
Форкнул себе.
При n = 7 там симметрия сохраняется.
Интересно, как тот человек сократил до 872 для n 6
vassabi
Эган — математик и писатель, а не программист. Ему — можно.
MaxVetrov
Первый форк!
Думаю, что там еще можно улучшения наделать.(дублирование кода, уменьшить проверку на деление).
Код не ООП, структуры и в 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
dcc0
Я вникаю в код, пока не все понял. То, что осознал пока: создается структура для n нод, потом от исходной перестановки (если я верно понял) справа налево прокручиваются варианты, то, что в последнем знаке добавляется к общей строке, так до исходной. Не могу понять, когда алгоритм доходит до предела одной ноды, как происходит выбор следующей. Как проверяется, что надо взять следующий фрагмент цепочки не с единицы, а с двойки…
Видимо, мне пока надо его на бумаге еще обдумывать.
dcc0
Еще мысли после чтения доказательства:
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.
catsmile
> Но только для n < 9,8 ? 10^42!
Ой, камон, да там просто тупо переполнение и всё. Какой-то идиот, писавший софт для Матрицы, решил, что 10^41 хватит всем, а лид прощёлкал.
eyno
Про интегралы Борвейна нашел даже на Хабре:
https://m.habr.com/post/146140/
А вот про те, что в статье, так и не нагуглилось.
AVI-crak
Лично я не вижу реального применения для операции перестановка в классическом математическом смысле этого действия. Хорошее упражнение для мозгов, но не более.
Дело в том что выполнять классическую перестановку для целого числа на Си — не имеет смысла. Оно от этого деградирует!!!
Можно и даже иногда нужно выполнять перестановку в двоичном виде. В этом случае целое число перестаёт быть числом, и становится парой структур под объединением — над ними уже можно издеваться без деградации.
Если у кого есть примеры использования классической перестановки над десятичными числами в РЕАЛЬНОЙ жизни — то прошу поделиться.
Мне интересно!!!
hippohood
Я как понимаю задача эквивалента какому-то классу задачи коммивояжера. А более важной задачи, полезной в бытовом практическом смысле, наверно и нет
AVI-crak
Вот по этому я и спросил конкретный случай применения!!! Но не эквивалент!!!
Потому как в задаче коммивояжера имя объекта не модифицируется.
А в классическом варианте перестановки — имя объекта является десятичное число. Само число в видимом десятичном представлении — имя. Как так?
И математики на полном серьёзе этим оперируют, что-то складывают и умножают.
Я не понимаю смысла — кто сможет мне объяснить!??
AVI-crak
Что и следовало доказать.
Простой вопрос, а ответа нету.
И кругом одни верующие фанатики.
MaxVetrov
Ну вот, например, есть применение перестановок
en.wikipedia.org/wiki/Permutation#Applications
Или что Вам нужно еще?
AVI-crak
Да, мне нужен пример в котором модифицируется имя объекта перестановки. И обязательно в десятичной системе.
Не диапазон имён множества объектов (список), не вариантность состояния в списке, а смену имени объекта перестановки в десятичном представлении.
Например вот такая ахинея
9=6 потому что количество спичек для составления цифр одинаково
123=321 потому что количество цифр одинаково
Если объектом перестановки является постоянное статическое имя — его всегда можно идентифицировать, управлять свойствами, добавлять/удалять зависимости, и прочее прочее прочее. Это я и сам умею и с успехом применяю.
Но если имя объекта представлено как десятичное многозначное число — начинается полная ахинея, которое я просто не понимаю.
MaxVetrov
Какое имя объекта? Вы о чем?
Десятичная система — это всего лишь форма представления числа.
Заверни число в двенадцатеричное представление ничего не изменится.
Ну если только умножать на 12, и делимость числа на 2,3,4,6,11,12 проверять в уме.)
И действительно, что Вы пишите по-моему не имеет никакого значения. Для чего Вам это нужно? Спички причем? Ну совпадает написание 6 и 9 если их перевернуть и что? Это всего лишь форма записи. Вставь вместо 0...9 — русский алфавит ничего не изменится.
AVI-crak
Когда число является значением константы или переменной — то всё в норме.
Но как только начинаются математические фокусы с перестановкой, то десятичное число превращается в имя. То самое место где оно записано имеет имя в десятичном выражении. Тот самый бред.
Я-бы ещё смирился, если-б то самое число считалось адресом. Но математики с умным видом меняют в этом числе цифры местами.!!! И это всё называется классическая перестановка в математике.
MaxVetrov
Я не совсем Вас понимаю. Каким образом, десятичное число превращается в имя по Вашему мнению?
Вы можете больше примеров привести в числовом виде?
У вас проблемы с десятиричной системой?
Попробуйте привести примеры для шестнадцатеричной, ну или любой какой хотите где таких проблем не наблюдается.
Также можете оперировать собачками, кошечками, спичками, если вам так удобнее, математики используют числа.
Вы смирится не можете, я вообще проблемы не наблюдаю.
Судя по тому что Вы написали 9=6.
То можно и 1+1=3 (купи 2 баночки пива 3 получи бесплатно), но это уже не математика — это маркетинг.
Можно и 9=54 (потому что цифру 9 можно составить из 5 спичек, а можно и из 4), что тоже не математика.(для записи)
AVI-crak
Зачем далеко ходить — вторая картинка темы. Её уже несколько раз повторили, но там она статична.
mayorovp
А где вы там видите число? Я там вижу просто набор цифр. Можете 1 2 3 заменить на x y z или на a1 a2 a3 — от этого ничего не поменяется.
Ktator
Фундаментальная наука на то и фундаментальная, что от неё не ждут мгновенного практического применения. Например, теорией чисел занимались несколько тысяч лет без какого-либо практического применения, а сейчас на ней криптография построена.
unalacuna
Можно ещё сократить
upd похоже что нет
maximw
В последней строке первые три перестановки 123, 231, 313. При этом 123 и 231 встречаются далее. Только 313 не встречается. Значит если сократить первые 2 символа сначала, то мы ничего не потеряем.
Ну или я что-то не так понял.
vics001
(123)[2(31]{2)(1[3}{2)1]3} — у меня тоже 12 получилось… хм…
MaxVetrov
А так нельзя?
231
312
213
132
321
ivan386
Если получается короче и со всеми вариантами то да. Собственно в статье Superpermutation есть этот вариант.
Для четырёх интереснее.
MaxVetrov
Он и в этой статье есть :)
Я только не понимаю почему народ здесь высчитавать начал без чтения статьи.
Видимо себя проверить.)
Для 4 надо проверить, какая там несостыковка. Хотя наверно лучше для 5 сначала, оно нечетное, возможно четность-нечетность имеет значение.
При n=5, возникает цикл. если следовать старому правилу.
Bronx
Близко к теме: A portmanteau of every word in English
mayorovp
Комментарий был удален