Конкурс Зиммерманна о перекладывании карт

[dvorkin_sacha]

Pavlovsky в сообщении #384886 писал(а):

Pavlovsky в сообщении #375881 писал(а):

Свойство №2 В перестановке с максимальным количеством ходов, ни одна карта не должна стоять на своей позиции. То есть не должно быть, чтобы карта с номером i стояла на позиции i.

Родилась такая вот задачка. Дано натуральное число N. Сколько перестановок из чисел от 1 до N удовлетворяют этому свойству?

Может быть легче пересчитать, сколько остается на своем месте и отнять от $n!$.
С практической точки зрения существует более интересная задача: найти достаточно точную оценку максимальному числу перекладывний. Я, например, нашел практический критерий, который у меня сбоя не дает (сужу по выложенной Nataly-Mak информации).

[Pavlovsky]

dvorkin_sacha в сообщении #384908 писал(а):

найти достаточно точную оценку максимальному числу перекладывний

maxl давал ссылку на статью. Статья совсем свежая 2010 год. В ней доказано, что нижняя оценка O(n^2). Так же в статье есть ссылка на статью Кнута, где докзывается верхняя оценка: Fn+1, (n+1)-е число Фибоначчи.

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

[dvorkin_sacha]

Pavlovsky

От этих оценок практического толку ноль, о чем, собственно говоря, и говорил maxal (а от оценки числами Фибоначчи можно вообще застрелиться на месте ). А по поводу обсуждения: нечего и обсуждать, т.к. я никакой конкретной информации не приводил (так сказать, обет молчания до окончания конкурса).

[Nataly-Mak]

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

Я вот позавчера не воспользовалась ситуацией, была прекрасная возможность при новом вводе всех результатов найти их долю по отношению к рекордам Jarek'а, который в данный момент является лидером конкурса. Это были бы точные значения. А я только для последних 4-х результатов, которые у меня были улучшены, это уловила.
Вот уточнённые рекорды для этих 4-х результатов:

n=41   1538
n=53   2833
n=59   4076
n=71   6272

Ну, вот и для всех $n$ примерно знаем полученные на конкурсе максимальные результаты, известно, к чему стремиться.

[svb]

Pavlovsky в сообщении #384886 писал(а):

Pavlovsky в сообщении #375881 писал(а):

Свойство №2 В перестановке с максимальным количеством ходов, ни одна карта не должна стоять на своей позиции. То есть не должно быть, чтобы карта с номером i стояла на позиции i.

Родилась такая вот задачка. Дано натуральное число N. Сколько перестановок из чисел от 1 до N удовлетворяют этому свойству?

Теорема 1. Число начальных последовательностей равно ближайшему целому числу к $\frac{{n!}}{e}$.
Число конечных последовательностей, для которых $m\left( a \right) > 0$ , равно ближайшему целому числу к $\left( {n - 1} \right)!\left( {1 - \frac{1}{e}} \right)$.
$m\left( a \right)$ - максимальная длина цепочки последовательностей, которые переходят в последовательность $a$.

[dvorkin_sacha]

dvorkin_sacha в сообщении #384393 писал(а):

Максимальная последовательность для порождения тождественной перестановки ($n=20$, расчет точный и занимающий всего пару минут) следующая:

$9, 16, 5 , 15, 8 ,14 ,1 ,10, 4 ,13 ,20, 18, 19, 11, 17, 2, 3, 12, 6, 7$

Число перекладываний - 224.

А вот единственная максимальная последовательность для порождения тождественной перестановки при $n=21$:

$8,17,10,12,1,11,13,3,18,9,2,14,20,5,19,15,21,6,4,7,16$

Число перекладываний - 255.

[Nataly-Mak]

На конкурсе некоторое затишье, активность немного снизилась, все уже устали после очень бурного старта.
Моей команде удалось выйти в десятку:

Rank  Score  Contestant  Last Improvement 

1 24.48 Jarek Wroblewski Wroclaw, Poland 8 Dec 2010 19:11
2 24.13 Markus Sigg Freiburg, Germany 7 Dec 2010 17:47
3 23.61 Igor Covganet Chisinau, Moldova 6 Dec 2010 14:24
4 23.57 Alex Chernov Penza, Russia 8 Dec 2010 17:14
5 23.07 Giuliano Bertoletti Parma, Italy 9 Dec 2010 08:27
6 22.26 Yirmy Yasovsky Rehovot, Israel 8 Dec 2010 20:31
7 21.94 Natalia Makarova Saratov, Russia 8 Dec 2010 22:26
8 21.88 Eugene Vasilchenko North Potomac, Maryland, United States 7 Dec 2010 19:36
9 21.84 Fred Mellender Rochester, New York, United States 6 Dec 2010 12:07
10 21.58 Kevin Burfitt Melbourne, Australia 8 Dec 2010 12:23

Удастся ли удержаться?
Радуюсь за россиянина, который на 4-ом месте. Молодец!

Два прежних лидера по-прежнему не восстанавливаются после пропажи базы данных. Не хотят?

[dvorkin_sacha]

Nataly-Mak

Вы писали о своих последних результатах (я их сейчас здесь не нашел):
n=23 325 - Ваш результат
n=23 384 - примерный максимальный

Дык вот: сей максимальный результат нехило отличается от единственного максимального решения, приводящего к тождественной перестановке (хотя он и выше Вашего результата). Вывод: постановка задачи Зоммерманом тупая (в том смысле, что в значительной своей части сводится к тупому перебору даже для хорошего алгоритма) и скорее подходит для дяди Васи из ЖЭК'а.

P.S.
При случае выложу свой результат на конкурсе и проверю истинность или ложность данного утверждения. О результатах отпишусь.

[svb]

dvorkin_sacha в сообщении #385313 писал(а):

Nataly-Mak
Вывод: постановка задачи Зоммерманом тупая (в том смысле, что в значительной своей части сводится к тупому перебору даже для хорошего алгоритма) и скорее подходит для дяди Васи из ЖЭК'а.

Т.е., если бы задача имела тривиальное решение, то она подходила бы для конкурса?

Цитата:

P.S.
При случае выложу свой результат на конкурсе и проверю истинность или ложность данного утверждения. О результатах отпишусь.

А вот это правильно! Но вот дядю Васю из ЖЭК'а вы вряд ли встретите на первом месте.

[dvorkin_sacha]

svb

У Вас что-то с логикой. Вот мои слова: "в значительной своей части сводится к тупому перебору даже для хорошего алгоритма". И где здесь о тривиальном алгоритме говорится? Хороший алгоритм дяде Васе не разработать, но протирать детали тупого компа, пока он перебирает варианты даже с помощью очень хорошего алгоритма,- это ему по силам. Я о чем: задачу необходимо формулировать так, чтобы суперкомпьютер и простой комп были поставлены в одинаковые условия. Вот, например, для тождественных перестановок я ее решил,- вот что-то в этом роде и надо предлагать.

[Nataly-Mak]

dvorkin_sacha в сообщении #385355 писал(а):

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

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

Цитата:

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

Я даже рядом не стояла с суперкомпьютером, у меня самый обычный компьютер, 2,4 Ггц. Но, тем не менее, задачу решаю и получаю не самые плохие результаты. При этом тупому перебору уделяю ровно столько, сколько это требуется в моём алгоритме наращивания последовательностей. И весь этот тупой перебор у меня выполняется считанные минуты, например, при переходе 79 -> 89. А при переходе 73 -> 79, например, 10-15 секунд.

Да, к тому же, как уже говорила, пишу программы на очень стареньком и тихоньком языке - Бейсике.

[dvorkin_sacha]

Nataly-Mak

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

[Nataly-Mak]

dvorkin_sacha в сообщении #385313 писал(а):

Nataly-Mak

Вы писали о своих последних результатах (я их сейчас здесь не нашел):
n=23 325 - Ваш результат
n=23 384 - примерный максимальный

Дык вот: сей максимальный результат нехило отличается от единственного максимального решения, приводящего к тождественной перестановке (хотя он и выше Вашего результата).

Если я правильно поняла, моё предположение о том, что последовательности, не привоядящие к тождественной перестановке, дают больше шагов, чем приводящие (для одного и того же $n$), верно (разумеется, при максимальных результататах в обоих случаях)

Далее, я предположила, что находить последовательности с максимальным результатом, приводящие к тождественной перестановке, проще, нежели не приводящие. То есть для тождественных перестановок проще разработать алгоритм.
svb сделал программу (разработал алгоритм) получения последовательностей, приводящих к тождественной перестановке. Я приводила здесь последовательность для $n=15$, полученную по этой программе.
Отмечала и тот факт, что недавно была найдена последовательность для $n=18$, приводящая к тождественной перестановке, тогда как последовательность в общем случае (с максимальным результатом) для данного $n$ пока не найдена.

Цитата:

При случае выложу свой результат на конкурсе и проверю истинность или ложность данного утверждения. О результатах отпишусь.

Давно пора! Можно и не ждать случая

-- Чт дек 09, 2010 19:33:09 --

dvorkin_sacha в сообщении #385384 писал(а):

Nataly-Mak

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

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

У моего товарища по команде svb тоже не суперкомпьютер, а самый обычный компьютер 1,8 Ггц. Программы он пишет на Турбо-Паскале.
Тем не менее, вчера вечером он прислал очень неплохие результаты, которые позволили подняться с занятого мной до этого 14-го места на 7-ое.

[Mathusic]

Pavlovsky в сообщении #384886 писал(а):

Pavlovsky в сообщении #375881 писал(а):

Свойство №2 В перестановке с максимальным количеством ходов, ни одна карта не должна стоять на своей позиции. То есть не должно быть, чтобы карта с номером i стояла на позиции i.

Родилась такая вот задачка. Дано натуральное число N. Сколько перестановок из чисел от 1 до N удовлетворяют этому свойству?

Это задача о нахождении количества беспорядков (описанные вами пер-ки). Их к-во выражается ф-лой $f(n)=\frac{n!}{0!}-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\dots +(-1)^n\frac{n!}{n!}$. Как видно, эта функция ведёт себя как $\frac{n!}{e}$ на бесконечности.

[dvorkin_sacha]

Nataly-Mak

Вы не обижайтесь, но я и назвал алгоритм, о котором вы говорите, алгоритмом с тупым перебором. А что касается алгоритма для получения тождественной последовательности, то интересно посмотреть результат, например, для n = 22: я ведь привел результаты для n = 20 и n = 21. А так это голословное утверждение.