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

[Nataly-Mak]

Так значит алгоритм наращивания даёт-таки рекордные последовательности?

А между тем продолжает пополняться таблица рекордов:

89 cards 11810 Hugo Pfoertner
Munich, Germany 16 Feb 2011 11:44 
12, 57, 8, 42, 31, 52, 67, 27, 23, 44, 3, 19, 47, 64, 58, 68, 18, 49, 30, 38, 66, 53, 45, 48, 56, 13, 20, 15, 26, 14, 51, 5, 54, 63, 72, 70, 24, 35, 9, 2, 33, 28, 34, 43, 6, 4, 65, 32, 55, 36, 25, 60, 21, 41, 39, 10, 7, 50, 17, 16, 22, 69, 61, 74, 75, 59, 40, 62, 11, 73, 76, 46, 37, 29, 78, 71, 88, 80, 84, 77, 86, 83, 81, 82, 87, 79, 89, 1, 85

[Pavlovsky]

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

Так значит алгоритм наращивания даёт-таки рекордные последовательности?

Рекордные в рамках текущего конкурса, но не теоретически максимальные.

-- Чт фев 17, 2011 13:06:36 --

К тому же непонято какие перестановки брать в качестве базовой для наращивания. Скажем в примере, приведенном выше, для N=53, базовая перестановка:
28: С = 442: 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,1,23,25
Абосолютно рядовая перестановка и очень далеко от рекорда для перестановок порядка 28. Подобных перестановок миллионы.

[Nataly-Mak]

Цитата:

Рекордные в рамках текущего конкурса, но не теоретически максимальные.

Ну о максимальных вообще речь не идёт, никто пока не заявил, что найденная им последовательность (рекордная на конкурсе) является максимальной. Как я уже писала, даже для $n=19$ неизвестно, является ли результат 221 максимальным.

Цитата:

К тому же непонято какие перестановки брать в качестве базовой для наращивания. Скажем в примере, приведенном выше, для N=53, базовая перестановка:
28: С = 442: 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,1,23,25
Абосолютно рядовая перестановка и очень далеко от рекорда для перестановок порядка 28. Подобных перестановок миллионы.

А вот тут как раз и нужна программа тотальной проверки последовательностей. Она проверяет все последовательности для данного $n$, какие у вас есть и потом ещё все, какие она сама получит в результате работы (все они очень методично записываются в рабочий файл программы, прямо ничего не надо делать, запустил программу и сиди книжечку почитывай). Это классная программа! Не устаю повторять - это восторг! Спасибо Х!
И вот удивительно как раз то, что очень часто улучшение получается как раз и не от последовательности с бОльшим числом шагов, а от последовательности с гораздо меньшим числом шагов.
Проверяются все последовательности! Добавляется от 6 до $m$ карт, $m$ задаётся как параметр.
К сожалению, быстродействие моего компьютера не позволило мне добавлять даже 12 карт, у меня максимально добавлялось 11 карт.
А у кого мощные компьютеры, да с многоядерными процессорами, то вообще можно по этой программе найти очень высокие результаты.

-- Чт фев 17, 2011 12:46:57 --

Яркий пример помню. Обрабатывала последоватьельности $n=79$; программа обрабатывает последовательности в порядке убывания количества шагов (начинает с самого большого результата, она сама ранжирует результаты, если они во входном файле заданы вразноброд); вот работала программа долго, у меня много было последовательностей $n=79$, порядка 300, улучшения не находилось, уже пошли очень маленькие количества шагов, я уже потеряла надежду на улучшение в этих переходах, и вдруг уже в самом почти конце массива последовательностей улучшение появилось для $n=89$ - 10410.

[dvorkin_sacha]

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

Забавно. Лидеры тоже пользовались алгоритмом наращивания!

Открыли Америку! Я об этом написал несколько дней назад и даже улучшил результат для n = 43. Вот Вы лучше попытайтесь найти принципиальные отличия в подходах 2-х первых лидеров. Но думаю, что эта задача Вам не "по зубам".

-- Чт фев 17, 2011 11:55:38 --

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

[А вот тут как раз и нужна программа тотальной проверки последовательностей.

Неа.

-- Чт фев 17, 2011 11:55:57 --

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

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

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

Я уже 100 лет назад написал, что там два решения.

[Pavlovsky]

Уважаемый dvorkin_sacha шел бы ты в жопу. Еще не хватало чтоб всякие недоноски терли об меня свои комплексы.

Недельный бан за хамство!

[dvorkin_sacha]

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

Уважаемый dvorkin_sacha шел бы ты в жопу. Еще не хватало чтоб всякие недоноски терли об меня свои комплексы.

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

Предупреждение за оффтопик!

[Vitaly12]

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

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

Уважаемый dvorkin_sacha шел бы ты в жопу. Еще не хватало чтоб всякие недоноски терли об меня свои комплексы.

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

Сначала спровоцировать, а потом довольно хмыкать - классический тролль (par excellence!).

Предупреждение за оффтопик!

[dvorkin_sacha]

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

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

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

Уважаемый dvorkin_sacha шел бы ты в жопу. Еще не хватало чтоб всякие недоноски терли об меня свои комплексы.

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

Сначала спровоцировать, а потом довольно хмыкать - классический тролль (par excellence!).

Ваша логика сродни поинманию Вами задачи о картах: т.е. никакой.

[Vitaly12]

Цитата:

Сначала спровоцировать, а потом довольно хмыкать - классический тролль (par excellence!).

Цитата:

Ваша логика сродни поинманию Вами задачи о картах: т.е. никакой.

Ч.Т.Д.

[whitefox]

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

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

Вы абсолютно правы. Проверка c+score[t]<score[n] излишняя.
Анализ алгоритма показывает, что всегда выполняется c+score[t]>=score[n].
Похоже Профессор перестраховался .

[Nataly-Mak]

Х пишет, что попробовал найти последовательность порядка 10000.

Цитата:

Часов через 5 программа дошла до 4633:[]:34014318: До 10000 нужно еще примерно 11 часов. Надоело ждать. Прервал.

Ещё он сообщил ссылку на интересную статью:

Цитата:

В статье http://habrahabr.ru/blogs/algorithm/102364/
показан интересный способ реверса массива.

[Nataly-Mak]

Новый рекорд у Зиммерманна:

89 cards 11829 Hugo Pfoertner
34, 39, 19, 43, 58, 57, 20, 41, 31, 6, 67, 18, 14, 46, 48, 12, 37, 33, 26, 17, 36, 32, 49, 29, 50, 8, 38, 65, 61, 55, 54, 63, 5, 13, 59, 47, 27, 62, 35, 30, 51, 74, 75, 21, 28, 9, 4, 69, 56, 66, 42, 7, 23, 10, 60, 44, 52, 40, 64, 68, 2, 45, 3, 72, 70, 24, 25, 16, 11, 73, 76, 15, 22, 53, 78, 71, 88, 80, 84, 77, 86, 83, 81, 82, 87, 79, 89, 1, 85

Теперь, когда все алгоритмы известны, все "секреты" раскрыты, желающие могут попробовать найти новые рекорды. Особенно те, кто не участвовал в конкурсе и не устал от задачи.
Я, например, до предела сыта задачей Уже вернулась к любимым квадратам. Он мне кажутся намного интересней этой задачи.

[Pavlovsky]

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

В статье http://habrahabr.ru/blogs/algorithm/102364/
показан интересный способ реверса массива.

Реализовал эту структуру данных. Чего то ничего не получилось. Все это работает ну очень медленно.

Кстати есть сомнения в эффективности и алгоритма Rokicki.

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

Ага. Есть все же некоторое улучшение

Достаточно посчитать количество выполняемых элементарных операций.

Алгоритм svb

 while j>i do begin
    b:=a[i];a[i]:=a[j];a[j]:=b;inc(i);dec(j)
  end;

Алгоритм Rokicki

b[first] += p ;
b[prev] -= p ;
b[p] += first - prev ;

prev = first ;
p = b[prev] ;
do {
next = b[p] - prev ;
prev = p ;
p = next ;
// this is a possible flip here
} until (p == N) ;

[svb]

Отправил для задачи 10K свое решение 203,216,214. На это понадобилось около 50 ч. работы моего "крутого" компьютера (Duron 1.8, RAM 256M). Для меньшей длины 166852535 удалось сократить время работы до 2.5 часов. В отличии от основного конкурса в 10K практически невозможно "дорабатывать" последовательности - даже простое вычисление длины цепочки кушает очень много времени.

[dvorkin_sacha]

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

Теперь, когда все алгоритмы известны, все "секреты" раскрыты...

Ой ли? Например, где написано, как за 16 часов на 4-х ядрах сделать наращивание для n = 30, используя 16!? Думаю, что до алгоритмов лидеров догадались многие участники конкурса, а вот до их грамотной реализации - нет.