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

[EtCetera]

Pavlovsky
Я, м.б., чего-то не понимаю, но OEIS недвусмысленно говорит о том, что Вы ошибаетесь. Сравните A000375 и A000376.
Впрочем, это уже неоднократно обсуждалось в этой теме.

[venco]

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

venco в сообщении #383102 писал(а):

Это доказательство лишь того, что в первой и последней позициях будут 1 и n соответственно.

Итак мы установили, что n в конечной перестановке будет стоять на позиции n. Аналагично рассуждаем для n-1 и так далее.

А дальше продолжать доказательство не получится, т.к. вот это:

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

Пусть в конечной перестановке на позиции n стоит число i. Это означает, что в начальной позиции число i тоже стояло на позиции n и в процессе инверсий своей позиции не меняло.

не верно для $n-1$ позиции. Она могла поменять место за счёт инверсии $n$.

[Nataly-Mak]

Излагаю свой алгоритм наращивания последовательностей, с помощью которого я получила неплохие результаты.
Вот, например, для последних $n$:

n=71  4912       
n=73  4991       
n=79  6333       
n=83  6956       
n=89  8598       
n=97  10668

Пусть мы имеем последовательность из $n$ карт:

a1, a2, a3, …, an

которая даёт $p$ шагов.
Результат перекладываний буду называть итоговой последовательностью.

Пусть итоговая последовательность для приведённой последовательности будет такой:

1, b2, b3, b4, …, bn

Теперь делаем переход от последовательности из $n$ карт к последовательности из $n+m$ карт.
Для новой последовательности перекладывания начинаем делать, исходя из итоговой последовательности. Составим последовательности такого вида:

x1, {b2, b3, b4, …,bn}, x2, x3, x4, …, xm+1

где x_1, x_2, x_3, …, x_{m+1} – любая перестановка из числа 1 и добавленных $m$ чисел, кроме перестановок, в которых x_1=1

Находим максимальное количество шагов для всех последовательностей такого вида, пусть это будет $q$ шагов. Тогда для колоды из $n+m$ карт мы получаем последовательность с $p+q$ шагами.

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

Кстати, уже для многих $n$ получила результаты больше предполагаемого максимума. В частности, для всех $n$, приведённых выше.

[Vitaly12]

Цитата:

Находим максимальное количество шагов для всех последовательностей такого вида, пусть это будет $q$ шагов. Тогда для колоды из $n+m$ карт мы получаем последовательность с $p+q$ шагами.

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

[Nataly-Mak]

Vitaly12 в сообщении #383347 писал(а):

Цитата:

Находим максимальное количество шагов для всех последовательностей такого вида, пусть это будет $q$ шагов. Тогда для колоды из $n+m$ карт мы получаем последовательность с $p+q$ шагами.

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

Пусть

x1, {b2, b3 ,... , bn}, x2, x3, ..., xm+1

найденная последовательность с максимальным количеством шагов $q$.
Замените в исходной последовательности для колоды из $n$ карт:

a1, a2, a3, ..., an

единицу на x_1 и припишите к ней $(x_2, x_3, ..., x_{m+1})$.
Вы получите последовательность для колоды из $n+m$ карт с количеством шагов $p+q$.

[dvorkin_sacha]

Nataly-Mak в сообщении #383165 писал(а):

Кстати, уже для многих $n$ получила результаты больше предполагаемого максимума. В частности, для всех $n$, приведённых выше.

Дело в том, что для больших $n$ и самый современный суперкомпьютер бессилен и поэтому предполагаемые максимумы - это слабая тень истинных максимумов. А вот для относительно небольших $n$ хороший алгоритм может дать неплохие результаты: например, для $n = 19$ можно получить истинный ответ за считанные минуты, если не секунды (3 совпадающих результата) .

[Vitaly12]

Цитата:

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

Я видно опять что-то не понимаю - разве для истинного ответа не нужно перебрать все перестановки (за вычетом тех, где номер и место совпадают)?
При $n = 19$ у меня на моем компьютере получаются совсем не секунды и даже не считанные минуты (((

[dvorkin_sacha]

Vitaly12 в сообщении #383654 писал(а):

Цитата:

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

Я видно опять что-то не понимаю - разве для истинного ответа не нужно перебрать все перестановки (за вычетом тех, где номер и место совпадают)?
При $n = 19$ у меня на моем компьютере получаются совсем не секунды и даже не считанные минуты (((

Выхода на кластер не имею. Ответ находится в следующем сообщении: post374955.html#p374955. Лично я, посмотрев на него, мгновенно понял, в каком направлении двигаться.

[dvorkin_sacha]

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

3 совпадающих результата .

Извиняюсь: не 3, а 1. Времени уже прошло много, поэтому запамятовал.

[Nataly-Mak]

Товарищ по команде прислал мне примерные наибольшие результаты, полученные на конкурсе:

n=19   220   202   
n =23   384   325   
n=29    662   584       
n=31    748   624    
n=37   1144     1029    
n=41   1422     1224     
n=43   1800     1325     
n=47    2171     1748     
n=53    2787     2158    
n=59    3809     2719 
n=61    4291     3449  
n=67    5270     3936  
n=71    6082     4912   
n=73    6477     5006  
n=79    8216     6345  
n=83    9032     6968  
n=89   11035     8711     
n=97   13230     10680

В последней колонке приведены полученные мной результаты.

Первоначально посчитанные мной предполагаемые максимумы для всех $n$ перекрыты, кроме $n=29$, у меня был предполагаемый максимум 669, но, может быть, я ошиблась в его вычислении.

-- Вс дек 05, 2010 09:37:09 --

Кстати, в Интернете есть готовая программа для решения задачи Зиммерманна. Автор алгоритма и программы - профессор D. E. Knuth.
Ссылка на страницу с программой приведена в OEIS, я увидела её сразу же, как в первый раз заглянула в Энциклопедию. Но программа написана на языке, которого я не знаю, и потому запустить программу не могу.

Некоторые товарищи опробовали программу. Говорят, что:
а) программа даёт максимальные результаты только для $n<17$;
б) для больших $n$ программа работает долго (несколько часов) и хороших результатов не даёт.

Однако интересно бы посмотреть на алгоритм, разработанный Кнутом.

Вот, например, последовательности для $n=16$, полученные по программе Кнута:

6 13 16 14 15 9 11 3 2 12 5 1 8 7 4 10
9 12 6 7 2 14 8 1 11 13 5 4 15 16 10 3

Первая последовательность приводит к тождественной перестановке (130 шагов), вторая не приводит к тождественной перестановке (139 шагов).

-- Вс дек 05, 2010 09:47:08 --

А это несколько результатов, полученных по программе Кнута для $n=18$:

156: 2 3 4 5 6 7 10 9 12 16 15 18 1 13 17 8 14 11 -> 1 5 8 7 6 2 4 3 9 
      10 11 12 13 14 15 16 17 18
      167: 2 3 4 5 6 8 17 10 13 7 1 15 11 9 12 18 14 16 -> 1 2 3 4 5 6 7 8 9 
      10 11 12 13 14 15 16 17 18
      167: 2 3 4 6 9 5 10 17 12 16 1 15 7 8 11 18 13 14 -> 1 7 4 6 12 13 8 2 3 
      9 11 10 5 14 15 16 17 18
      173: 2 3 4 7 10 9 6 13 14 8 16 17 5 1 18 15 12 11 -> 1 5 8 7 6 2 4 3 9 
      10 11 12 13 14 15 16 17 18
      173: 2 3 4 12 18 15 9 7 13 11 5 6 17 10 8 1 16 14 -> 1 13 12 11 7 6 5 2 
      3 4 8 9 10 14 15 16 17 18
      174: 2 3 4 12 18 15 5 11 13 7 9 6 17 10 8 1 16 14 -> 1 13 12 11 7 6 5 2 
      3 4 8 9 10 14 15 16 17 18

Может быть, анализируя эти результаты, удастся проникнуть в алгоритм Кнута.

[dvorkin_sacha]

Nataly-Mak в сообщении #383731 писал(а):

... программа даёт максимальные результаты только для $n<17$
...

6 13 16 14 15 9 11 3 2 12 5 1 8 7 4 10
9 12 6 7 2 14 8 1 11 13 5 4 15 16 10 3

Первая последовательность приводит к тождественной перестановке (130 шагов), вторая не приводит к тождественной перестановке (139 шагов).

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

[dvorkin_sacha]

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

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

Кстати, для $n = 19$ основное решение тоже нетождественное.

[Nataly-Mak]

Ещё раз о последовательностях, приводящих и не приводящих к тождественной перестановке.

Вот последовательность из OEIS для $n=18$, приводящая к тождественной перестановке:

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

Эта последовательность даёт 191 шаг.

Вот последовательность для $n=18$ тоже приводящая к тождественной перестановке:

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

167 шагов.

Как видим, последовательностей, приводящих к тождественной перестановке, может быть несколько, и не все такие последовательности дают максимальный результат.

Как я поняла, последовательность для $n=18$, не приводящая к тождественной перестановке, неизвестна.

Вопрос: всегда ли последовательность, не приводящая к тождественной перестановке, даёт не меньше шагов, чем последовательность, приводящая к тождественной перестановке (имеются в виду последовательности с максимальными результатами)? Скорее всего, да. По крайней мере, для последовательностей из OEIS это так.

Думаю, что последовательность с максимальным количеством шагов, приводящую к тождественной перестановке, найти проще, чем не приводящую.
Вот недавно была найдена такая последовательность для $n=18$.
По всей видимости, для такого случая проще разработать алгоритм поиска последовательности.

[Mathusic]

Nataly-Mak в сообщении #384073 писал(а):

Как я поняла, последовательность для $n=18$, не приводящая к тождественной перестановке, неизвестна

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

Nataly-Mak в сообщении #384073 писал(а):

Вопрос: всегда ли последовательность, не прияводящая к тождественной перестановке, даёт не меньше шагов, чем последовательность, приводящая к тождественной перестановке?

Нет. Например для $n=3$ обе максимальные последовательности обращаются в тождественные.

[Nataly-Mak]

Mathusic в сообщении #384084 писал(а):

Nataly-Mak в сообщении #384073 писал(а):

Вопрос: всегда ли последовательность, не прияводящая к тождественной перестановке, даёт не меньше шагов, чем последовательность, приводящая к тождественной перестановке?

Нет. Например для $n=3$ обе максимальные последовательности обращаются в тождественные.

Я имела в виду последовательности для тех $n$, для которых существуют последовательности обоих видов: приводящие и не приводящие к тождественной перестановке. Когда последовательность одного вида не существует, сравнивать нечего, вопрос становится бессмысленным.