2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 16  След.
 
 Re: Новый конкурс Зиммерманна
Сообщение03.12.2010, 15:19 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение03.12.2010, 17:15 
Заслуженный участник


04/05/09
4562
Pavlovsky в сообщении #383114 писал(а):
venco в сообщении #383102 писал(а):
Это доказательство лишь того, что в первой и последней позициях будут 1 и n соответственно.


Итак мы установили, что n в конечной перестановке будет стоять на позиции n. Аналагично рассуждаем для n-1 и так далее.
А дальше продолжать доказательство не получится, т.к. вот это:
Pavlovsky в сообщении #383077 писал(а):
Пусть в конечной перестановке на позиции n стоит число i. Это означает, что в начальной позиции число i тоже стояло на позиции n и в процессе инверсий своей позиции не меняло.
не верно для $n-1$ позиции. Она могла поменять место за счёт инверсии $n$.

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение03.12.2010, 17:30 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Излагаю свой алгоритм наращивания последовательностей, с помощью которого я получила неплохие результаты.
Вот, например, для последних $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$, приведённых выше.

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение04.12.2010, 02:12 


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


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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение04.12.2010, 05:48 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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$.

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение04.12.2010, 21:26 


04/11/10

141
Nataly-Mak в сообщении #383165 писал(а):
Кстати, уже для многих $n$ получила результаты больше предполагаемого максимума. В частности, для всех $n$, приведённых выше.

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение05.12.2010, 00:13 


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

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение05.12.2010, 00:49 


04/11/10

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

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

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение05.12.2010, 06:30 


04/11/10

141
dvorkin_sacha в сообщении #383588 писал(а):
3 совпадающих результата .

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение05.12.2010, 08:23 
Заблокирован
Аватара пользователя


22/03/08

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

Код:
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

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение05.12.2010, 12:10 


04/11/10

141
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$ роль нетождественных перестановок увеличивается.

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение05.12.2010, 14:14 


04/11/10

141
dvorkin_sacha в сообщении #383776 писал(а):
С ростом $n$ роль нетождественных перестановок увеличивается.

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение05.12.2010, 23:03 
Заблокирован
Аватара пользователя


22/03/08

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

Вот последовательность из 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$.
По всей видимости, для такого случая проще разработать алгоритм поиска последовательности.

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение05.12.2010, 23:24 
Аватара пользователя


14/08/09
1140
Nataly-Mak в сообщении #384073 писал(а):
Как я поняла, последовательность для $n=18$, не приводящая к тождественной перестановке, неизвестна

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

Nataly-Mak в сообщении #384073 писал(а):
Вопрос: всегда ли последовательность, не прияводящая к тождественной перестановке, даёт не меньше шагов, чем последовательность, приводящая к тождественной перестановке?

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

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение06.12.2010, 00:41 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Mathusic в сообщении #384084 писал(а):
Nataly-Mak в сообщении #384073 писал(а):
Вопрос: всегда ли последовательность, не прияводящая к тождественной перестановке, даёт не меньше шагов, чем последовательность, приводящая к тождественной перестановке?

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 229 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 16  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group