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

[dvorkin_sacha]

(Оффтоп)

Не я первый начал. Но если даже и не читаете, то это не повод для написания всякой несуразицы.

[Pavlovsky]

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

Pavlovsky
вы поняли, как именно Кнут использует предыдущие рекордные последовательности? Это очень интересный вопрос.

Кнут исползует не предыдущие рекордные последовательности, а собственно рекордное число инверсий.

Вот фрагмент кода из алгоритма Кнута.

if (k==t) {
  for (t=1;a.q[t]==k-t;t++);
  if (c+score[k-t]<score[n]) goto infeas;
}@+else if (c+score[t]<score[n]) goto infeas;

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

В коде Кнута смущает, что рекорды он проверяет дважды: c+score[k-t]<score[n] и c+score[t]<score[n]. Чего то я не догоняю.

[Nataly-Mak]

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

Стефано пишет мне, что народ на сайте Зиммерманна говорит о целесообразности опубликовать максимальные последовательности для всех $n$, а не только для простых.
В самом деле, это было бы неплохо.
У меня, например, в БД максимальные последовательности для всех $n$, так их находит программа Х, так они и записываются в файл result.txt.

Например, до сих пор неизвестна максимальная последовательность для $n=18$ (может, только мне неизвестна), не приводящая к тождественной перестановке. Предполагаю, согласно моей гипотезе, что результат для такой последовательности будет не меньше 191 шагов. И далее для n=20, 21, 22 тоже неизвестны максимальные последовательности для общего случая.

-- Ср фев 16, 2011 11:41:48 --

Вот небольшой фрагменn нашей БД:

20:[]:249: 2,8,11,6,19,17,13,7,18,3,9,20,15,1,12,4,10,14,5,16
21:[]:269: 4,7,16,6,17,3,10,13,8,5,21,15,11,12,2,9,14,20,18,1,19
22:[]:291: 2,9,16,3,13,5,10,15,7,21,14,18,22,20,12,6,19,4,8,1,11,17
23:[]:370: 4,17,5,12,11,14,19,22,6,21,9,15,10,7,2,13,1,23,20,16,3,8,18
24:[]:371: 4,17,5,12,11,14,19,22,6,21,9,15,10,7,2,13,24,23,20,16,3,8,18,1
25:[]:400: 8,16,13,7,14,12,15,3,2,4,23,10,5,22,6,9,1,24,20,11,25,19,17,21,18
26:[]:442: 3,18,12,15,17,16,20,22,26,11,14,13,4,8,19,5,2,7,21,6,10,9,25,1,23,24
27:[]:477: 2,7,8,19,16,12,5,9,13,17,20,18,10,11,14,3,4,26,6,15,23,27,24,25,1,21,22
28:[]:549: 8,17,24,1,18,9,10,2,13,11,3,14,12,4,16,23,5,20,6,7,25,28,26,15,27,22,21,19
29:[]:609: 7,16,17,18,9,21,6,22,20,11,13,2,8,10,4,15,5,12,27,3,14,19,28,26,1,29,25,24,23
30:[]:634: 3,6,4,7,17,11,9,22,13,14,10,8,2,5,19,24,15,23,21,16,18,12,26,20,30,29,28,1,25,27

Кстати, программа Х работала у меня буквально до последней минуты конкурса. В 18.58 выдала последнее улучшение для $n=58$ - 3567 шагов. В 19.00 я остановила программу и пошла смотреть финал конкурса.
Последнее улучшение для простого $n$ было найдено программой 3 февраля. Таким образом, мне хватило моего алгоритма на весь конкурс и возможности его далеко не исчерпаны. Можно было бы найти ещё немало улучшений, если добавлять не 10-11 карт максимально, как это делала я, а хотя бы 12-13.
В программе Х наращивание последовательностей хорошо оптимизировано с учётом первых-первых чисел, поэтому перебор идёт не тупо, что даёт значительный выигрыш времени.

[Pavlovsky]

Nataly-Mak
Суть вашего алгоритма хорошо видна на примере перестановки:

29:[]:609: 7,16,17,18,9,21,6,22,20,11,13,2,8,10,4,15,5,12,27,3,14,19,28,26,1,29,25,24,23
Ниже представлена перестановка первых-первых для этой перестановки:
FFRONT()= (7,6,16,15,17,5,10,20,3,12,4,9,2,8,21,14,18,13,22,19,11)+(27,25,28,24,26,29,23)

Перестановка первых-первых разбивается на две части. Сначала в последовательности первых чисел появляются числа от 2 до 22. А затем к полученной перестановке добавляются числа от 23 до 29.
Парадоксально, но факт такой алгоритм дал хорошие результаты. Почему? Для меня до-сих пор загадка.

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

Гипотеза. Перестановку первых-первых чисел рекордной перестановки нельзя разбить на две части: (перестановка чисел от 2 до к)+(перестановка чисел от k+1 до n).

[Nataly-Mak]

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

Парадоксально, но факт такой алгоритм дал хорошие результаты. Почему? Для меня до-сих пор загадка.

А почему парадоксально?

Цитата:

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

Гипотеза. Перестановку первых-первых чисел рекордной перестановки нельзя разбить на две части: (перестановка чисел от 2 до к)+(перестановка чисел от k+1 до n).

Это интересная гипотеза. Исходя из этой гипотезы, можно утверждать, что алгоритм наращивания последовательностей не может дать максимальную перестановку. Я правильно поняла?
А если этот алгоритм работает вместе с алгоритмом поиска вглубь?
----------
Tomas Rokicki продолжает побивать рекорды:

43 cards 2009 Tomas Rokicki
12, 28, 13, 21, 26, 11, 15, 22, 2, 4, 20, 18, 23, 9, 24, 7, 27, 3, 16, 14, 25, 5, 8, 6, 17, 30, 19, 10, 33, 34, 38, 42, 41, 37, 39, 32, 29, 31, 36, 43, 35, 1, 40
61 cards 4858 Tomas Rokicki
4, 54, 7, 25, 28, 17, 35, 42, 15, 31, 46, 51, 1, 56, 58, 21, 47, 2, 37, 9, 3, 12, 49, 43, 19, 50, 36, 30, 8, 38, 23, 33, 13, 24, 20, 41, 16, 27, 45, 39, 11, 6, 52, 14, 29, 34, 10, 55, 22, 40, 44, 60, 32, 48, 18, 5, 59, 26, 61, 57, 53

[Pavlovsky]

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

А если этот алгоритм работает вместе с алгоритмом поиска вглубь?

Вот примеры луших результатов нашей команды.
29: 7,16,17,18,9,21,6,22,20,11,13,2,8,10,4,15,5,12,27,3,14,19,28,26,1,29,25,24,23
FFRONT= (7,6,16,15,17,5,10,20,3,12,4,9,2,8,21,14,18,13,22,19,11)+(27,25,28,24,26,29,23)

31: 4,17,5,12,11,14,19,22,6,21,9,15,10,7,2,13,26,23,20,16,3,8,18,28,1,29,31,30,25,24,27
FFRONT=(4,12,15,2,7,6,11,5,10,14,9,22,8,19,20,3,21,16,13,17,23,18)+(26,29,25,31,27,28,24,30)

37: 8,16,13,7,14,12,15,3,2,4,23,10,5,22,6,9,30,24,20,11,25,19,17,21,18,33,36,29,1,34,26,28,35,31,32,37,27
FFRONT=(8,3,12,10,7,2,4,16,9,6,5,14,13,15,22,19,20,23,17,11,24,21,25,18)+(30,34,31,36,37,27,33,29,26,28,35,32)

Как видите поиск в глубину ничего дополнительного не дал.

-- Ср фев 16, 2011 15:28:27 --

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

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

Поняли правильно. Только уточню это всего лишь гипотеза.

[Nataly-Mak]

Вот посмотрите на последовательность, которая получена по программе наращивания последовательностей (как раз это было последнее, полученное мной улучшение, работала от последовательностей $n=50$, добавляла максимально 9 карт):

58:[]:3542: 56,52,51,57,55,58,47,54,46,50,43,41,36,44,30,32,37,45,42,48,49,11,5,10,22,23,21,15,17,28,24,19,7,14,16,12,2,3,6,4,9,13,8,27,33,20,26,18,25,35,40,34,38,31,39,29,1,53

Здесь результат 3542, потом с помощью отдельной программы поиска вглубь этот результат был улучшен до 3567 шагов.

Я не вижу в приведённой последовательности привычного для наращенных последовательностей окончания. Будет ли для этой последовательности выполняться разделение перестановки первых-первых чисел на две группы, как вы показали выше?

-- Ср фев 16, 2011 15:08:48 --

Это окончательный результат (улучшение при помощи отдельной программы поиска вглубь):

58:[]:3567: 42,48,33,20,26,18,25,31,39,37,23,6,32,16,10,5,27,9,13,12,8,35,40,34,38,49,56,52,51,57,55,58,47,54,46,50,43,29,41,36,44,30,45,19,24,28,21,7,22,17,15,11,2,4,14,3,1,53

Тут уже вообще не видно, что к чему добавлялось.

[Pavlovsky]

58:[]:3542: 56,52,51,57,55,58,47,54,46,50,43,41,36,44,30,32,37,45,42,48,49,11,5,10,22,23,21,15,17,28,24,19,7,14,16,12,2,3,6,4,9,13,8,27,33,20,26,18,25,35,40,34,38,31,39,29,1,53

Здесь какая то ошибка эта перестановка не является результатом наращивания. Число 56 при наращивании никак не может быть на первом месте.


58:[]:3567: 42,48,33,20,26,18,25,31,39,37,23,6,32,16,10,5,27,9,13,12,8,35,40,34,38,49,56,52,51,57,55,58,47,54,46,50,43,29,41,36,44,30,45,19,24,28,21,7,22,17,15,11,2,4,14,3,1,53
FFRONT=42,30,32,23,35,31,49,22,6,9,10,16,19,48,56,3,4,2,14,13,11,8,17,7,12,5,27,45,29,28,41,15,21,18,25,20,26,24,33,38,37,34,40,36,39,44,46,43,50,47,54,51,55,52,58,53,57

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

[Nataly-Mak]

Ещё раз копирую из рабочего файла программы эту последовательность (благо рабочий файл у меня ещё жив):

58:[]:3542: 56,52,51,57,55,58,47,54,46,50,43,41,36,44,30,32,37,45,42,48,49,11,5,10,22,23,21,15,17,28,24,19,7,14,16,12,2,3,6,4,9,13,8,27,33,20,26,18,25,35,40,34,38,31,39,29,1,53

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

Почему же число 56 по-вашему не может быть на первом месте?
К исходной последовательности для $n=50$ добавляется 8 карт: 51, 52, 53, 54, 55, 56, 57, 58.

[dvorkin_sacha]

Я уже писал по поводу n = 43. Выдалась свободная минута - посмотрел на рекордное решение более внимательно и обнаружил прокол. Через 20 минут получил 2 решения с числом перекладываний 2009.

[Pavlovsky]

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

Код:
58:[]:3542: 56,52,51,57,55,58,47,54,46,50,43,41,36,44,30,32,37,45,42,48,49,11,5,10,22,23,21,15,17,28,24,19,7,14,16,12,2,3,6,4,9,13,8,27,33,20,26,18,25,35,40,34,38,31,39,29,1,53

Понял эту перестановку надо перелистнуть на шаг вперед.
58: 29,39,31,38,34,40,35,25,18,26,20,33,27,8,13,9,4,6,3,2,12,16,14,7,19,24,28,17,15,21,23,22,10,5,11,49,48,42,45,37,32,30,44,36,41,43,50,46,54,47,58,55,57,51,52,56,1,53
FFRONT = 29,15,13,28,39,45,41,11,7,23,8,3,4,9,2,6,12,14,5,10,17,16,22,21,19,18,25,20,26,27,24,33,38,30,37,34,32,35,31,40,36,44,42,48,46,43,50,47,49,54,51,55,52,58,53,57,56

[Nataly-Mak]

Цитата:

Понял эту перестановку надо перелистнуть на шаг вперед.

Ну вот, значит всё чётко и у меня, и у вас, что очень приятно

[Nataly-Mak]

В OEIS добавлен результат 207 последовательности для $n=19$.
A000376

[Nataly-Mak]

Существуют последовательности с результатом 207, не приводящие к тождественной перестановке, вот одна из них (результат svb):

n=19:207: 2  5  10  8  6  3  9  4  12  17  14  7  18  16  19  13  11  1  15

Интересно отметить, что итоговая последовательность у этого решения точно такая же, как в одном из решений, найденных по программе Кнута:

n=19:193: 2 3 4 5 6 9 12 17 8 11 10 7 18 16 13 19 14 1 15 -> 1 13 12 11 10 6 5 4 2 3 7 8 9 14 15 16 17 18 19

А вот по поводу того, является ли максимумом результат 221 для $n=19$, "молчит наука"

[Pavlovsky]

Забавно. Лидеры тоже пользовались алгоритмом наращивания!
53: 12,8,14,19,9,2,22,15,17,13,16,3,6,5,11,4,7,21,10,26,24,20,27,18,28,34,23,25,32,33,29,41,30,31,40,38,44,39,49,43,35,37,36,51,42,53,1,52,50,45,46,48,47

FFRONT=12,3,13,6,9,15,11,2,16,4,5,17,7,14,8,19,10,(21,24,18,20,22,27,23,26,28,25),(34,31,32,33,29,30),(41,35,43,36,37,39,40,38,44,51,46,50,45,42,49,52,48,53,47)

Можно видеть аж две процедуры наращивания в чистом виде и одну немного сглаженную(выпадает число 19). При последней процедуре наращивания добавлено аж 19 чисел!