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
4596
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, Супермодераторы



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

Сейчас этот форум просматривают: Dmitriy40


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

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