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

[dvorkin_sacha]

Я разгадал алгоритм Jarek'а. Что касается моего алгоритма, то он пригоден только для небольших n, поэтому (и не только поэтому) я и не стал выкладывать его. Мои результаты для n = 29 и 31 выше финальных результатов конкурса, но для n = 23 у меня более чем 382 результат не получался, поэтому я и заподозрил давно ошибку в опубликованном ранее результате 384.

[svb]

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

Что касается моего алгоритма, то он пригоден только для небольших n, поэтому (и не только поэтому) я и не стал выкладывать его. Мои результаты для n = 29 и 31 выше финальных результатов конкурса, но для n = 23 у меня более чем 382 результат не получался, поэтому я и заподозрил давно ошибку в опубликованном ранее результате 384.

А я так ждал! "Не получался" - это доказательство?

[Nataly-Mak]

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

Мои результаты для n = 29 и 31 выше финальных результатов конкурса...

Может, покажете эти результаты?
А то на протяжение всей темы только одно хвастовство от вас исходит

[dvorkin_sacha]

Nataly-Mak

Необходимо ворочить своими мозгами, а не подбирать крошки с чужого стола, как это делаете Вы (например, я говорю о решении для n = 19, которое я здесь опубликовал с пояснениями, и которое Вы включили в результаты конкурса). Я также подтверждал и наличие решения 382 для n = 23. Кроме того я опубликовал решения для n = 20 и n = 21, а также для n = 21 при решении 207. Также я указал на наличие 3-х решений для случая n = 29. Что касается алгоритма Jarek'а, то я могу описать его подход к проблеме с его согласия. И это от Вас исходит неуемное многословное хвастовство и распирают неподтвержденные результатами амбиции.

-- Пн фев 14, 2011 10:59:58 --

svb в сообщении #412758 писал(а):

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

Что касается моего алгоритма, то он пригоден только для небольших n, поэтому (и не только поэтому) я и не стал выкладывать его. Мои результаты для n = 29 и 31 выше финальных результатов конкурса, но для n = 23 у меня более чем 382 результат не получался, поэтому я и заподозрил давно ошибку в опубликованном ранее результате 384.

А я так ждал! "Не получался" - это доказательство?

Конечно не доказательство, как и некое утверждение господина, занявшего второе место, которому, как я понял, Вы поверили: я тоже мог представиться Папой Римским.

[Nataly-Mak]

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

...например, я говорю о решении для n = 21, которое я здесь опубликовал с пояснениями, и которое Вы включили в результаты конкурса

???
$n=21$ вообще не входит в конкурсную задачу.

Я все свои результаты опубликовала.
А вот вы не хотите опубликовать ваши результаты, которые выше, чем на конкурсе. Теперь-то у вас их никто не украдёт, конкурс закончился

-- Пн фев 14, 2011 12:35:30 --

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

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

Максимальная последовательность для порождения тождественной перестановки ($n=20$, расчет точный и занимающий всего пару минут) следующая:

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

Число перекладываний - 224.

А вот единственная максимальная последовательность для порождения тождественной перестановки при $n=21$:

$8,17,10,12,1,11,13,3,18,9,2,14,20,5,19,15,21,6,4,7,16$

Число перекладываний - 255.

Вы эту последовательность для $n=21$ имели в виду?
И куда же я её включила?
Результат нашей команды для данного $n$ равен 269:

21:[]:269: 4,7,16,6,17,3,10,13,8,5,21,15,11,12,2,9,14,20,18,1,19

[dvorkin_sacha]

Nataly-Mak

Что Вы все передергиваете? Вы ведь прекрасно знаете, о чем я говорю: об описке, которую я исправил для n = 19 и о решении для n = 20 в случае конечной тождественной последовательности. А не публикую свои результаты для n = 23, 29, 31 по одной простой причине: как я с легкостью установил подход Jarek'а к решению данной проблемы, так и особо мозговитые могут по моему решению понять, до чего я додумался.

[Nataly-Mak]

Так, давайте говорить серьёзно!

Ничего "прекрасно" не знаю и не понимаю, о чём вы говорите.

Я вам дала ответ о последовательности для $n=21$, о которой вы написали в предыдущем посте, привела цитату из вашего поста, ничего не передёргивая. Там однозначно написано, что я "включила в результаты конкурса" вашу последовательность для $n=21$. Повторить цитату? Или вы, наконец, будете отвечать за свои слова??!
Теперь вы говорите о последовательностях для $n=19$ и $n=20$ и о каких-то описках. Пожалуйста, изъясняйтесь понятно и без описок.

Результат для $n=19$ (221 шаг) найден svb ещё до того, как вы здесь опубликовали свои результаты (он может это подтвердить).

Последовательности для n=20 в конкурсную задачу не входят.
Думайте немного головой, прежде чем обвинять людей в том, чего они не делали.

Вижу, что вы исправили в том посте последовательность $n=21$ на последовательность $n=19$. Значит, вы обвиняете меня в том, что я включила ваш результат для $n=19$ в результаты конкурса? Так?
А вы уверены в том, что я действительно это сделала?
Как я уже написала, результат этот найден svb задолго до вашей публикации.

[dvorkin_sacha]

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

Результат для $n=19$ (221 шаг) найден svb ещё до того, как вы здесь опубликовали свои результаты (он может это подтвердить).

Задним числом я могу и Папой Римским представиться. Уверен, что опубликуй я свое решение для n = 23, то основываясь на Вашей беспардонности, могу предположить, что ответ был бы аналогичным (почему я этот результат не опубликовал, написано выше). И мои замечания касались не конкурса, а Вашего утверждения по поводу моего "хвастовства": одна моя строчка информации перекрывает все Ваши многочисленные словесные излияния. Да, еще забыл упомянуть (я об этом ранее писал) об интересном экстремальном решении для n = 23.

[Nataly-Mak]

Привожу фотографию своего почтового ящика, на которой видно, когда получено письмо от svb с результатом для последовательности $n=19$:



Вы опубликовали свои последовательности для $n=19$ 13 января.
Как видите, ваши обвинения явная ложь.

[dvorkin_sacha]

Nataly-Mak

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

[Nataly-Mak]

Цитата:

Уверен, что опубликуй я свое решение для n = 23, то основываясь на Вашей беспардонности, могу предположить, что ответ был бы аналогичным...

Прошу вас прекратить оскорбления и необоснованные обвинения в мой адрес!!!

Я доказала вам, что svb получил результат для $n=19$ раньше, чем вы его опубликовали.

-- Пн фев 14, 2011 13:40:59 --

Ах, вы обвиняете меня ещё и в подтасовке фактов!
Тогда ещё одна фотография:



Продолжаете настаивать на своём обвинении?

[Vitaly12]

Цитата:

Прошу вас прекратить оскорбления и необоснованные обвинения в мой адрес!!!

Да ведь уже ясно, что просто хвастал и никакого "супералгоритма" у него нет!

[Pavlovsky]

Приятно, что популярность конкурса Зиммерманна растет среди россиян. В двадцатке первых аж три россиянина.

[svb]

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

Да ведь уже ясно, что просто хвастал и никакого "супералгоритма" у него нет!

Вот тут вы не правы. По многим признакам было понятно, что это не просто "хвастовство". Существования "критерия максимальности" исключать нельзя, но, похоже, пока мы не можем ни доказать, ни опровергнуть этого. Результаты конкурса еще предстоит изучать, но уже сейчас видно, что в основе лучших результатов лежали модифицированные алгоритмы поиска вперед и поиска назад, идущие еще от алгоритмов Кнута. Идеи Моралес пока не удалось реализовать. И, хотя мы и проиграли, я до сих пор в восторге от идеи Павловского о п.п. последовательностях, о которой у победителей нет упоминаний (возможно я их пока не увидел). Эксперименты с простейшей п.п.п.: 2,3,4,...,n,1 дают надежду на существование некоторых глубинных свойств. Конечно, одни и те же вещи можно представлять различными способами и некоторые могут использовать другие представления. А на dvorkin_sacha у меня были большие надежды.

[Pavlovsky]

Увы в этот раз мне не удалось помочь команде. Так все время и просидел на скамейке запасных.
Но упрекнуть себя мне не в чем.
1)Я честно до последнего дня бился над задачей.
2) Задача сформулирована Конвеем в 1970 году. За 40 лет проффесинальные математики смогли придумать алгоритм Кнута (с помощью которого смогли осущствить полный перебор для n=18) и сформулировать квадратичную нижнюю оценку. Так что ничего удивительного, что математик-любитель не смог сделать больше всего за два месяца.

Выкладываю свои теоретические наработки.

http://newest.ifolder.ru/21890586 осторожно файл 1.5м

Цитата:

от идеи Павловского о п.п

Полагаю, что это идея Кнута. В алгоритме Кнута я так до конца и не разобрался. Но перебор он начинает с перестановки 2,3,4,...,n,1, которая является первой в лексикографическом порядке перестановок первых-первых чисел.

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