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

[Nataly-Mak]

Цитата:

А на dvorkin_sacha у меня были большие надежды.

Напрасно надеялись. Вот вам, как "особо мозговитому", он ни за что не покажет свои решения

[Pavlovsky]

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

Я разгадал алгоритм Jarek'а.

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

Что касается алгоритма Jarek'а, то я могу описать его подход к проблеме с его согласия.

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

я с легкостью установил подход Jarek'а к решению данной проблемы

Хороший клоун dvorkin_sacha. Надо этими сентенциями я посмеялся от души. Чего скрывать если Jarek уже выложил описание своего алгоритма.
http://www.math.uni.wroc.pl/~jwr/TopSwops/

-- Пн фев 14, 2011 17:58:38 --

http://tech.groups.yahoo.com/group/AlZi ... ssage/5027

Это словесное описание алгоритма.

[Nataly-Mak]

svb
вы считаете, что алгоритм у dvorkin_sacha есть?
Так что вам мешает разгадать его, как он разгадал алгоритм Jarek'а?
Ведь он так много выложил уже решений, для n=19,20,21. Для n=23 подтвердил существование результата 382, значит, последовательность с таким результатом он тоже нашёл. Разве этого вам ещё мало?

[Pavlovsky]

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

вы считаете, что алгоритм у dvorkin_sacha есть?

К гадалке не ходи. Алгоритм простой. Берется конечная тривиальня перестановка (1,2,3,...n). И обратным перебором ищется начальная перестановка. Ну еще должны быть какие то эвристики. Иначе даже для n=23 алгоритм будет крутиться очень долго.

[dvorkin_sacha]

Pavlovsky

Апломба у Вас много, а идеи все отдают "тупизной". За информацию спасибо: я этого не знал, да и мне некогда следить. Случайно про использованное железо там не говорится? А по поводу клоуна: это Вам к Высоцкому, так как прям про Вас.

-- Пн фев 14, 2011 19:36:44 --

svb

Я совершенно не сомневаюсь в том, что вы посчитали n = 19. Просто не люблю, когда провоцируют (это не про Вас). Удивлен,что Вам не удалось осилить n = 29 (я говорю о результате с 655 перекладываниями). Да и результат 382 для n = 23 можно получить классическим путем без всяких вывертов. А о том, что я получил результат близкий к 700 для n = 29, я писал, когда еще не был известен результат 689. Что касается результата 689, то нетрудно усмотреть, что там использовался факториал от 16 (тоже относится и к результату для n = 43, только использование 16! видно сразу невооруженным взглядом, чего не скажешь о n = 29).

-- Пн фев 14, 2011 19:55:21 --

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

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

У меня полный перебор для факториал от 15 при n = 25 на четырех ядрах занимет порядка 4-х часов.

[dvorkin_sacha]

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

svb
Что касается результата 689, то нетрудно усмотреть, что там использовался факториал от 16

Высвободилось время: посмотрел. И оказалось, что все сводится к 13! Теперь мне стало ясно, почему мой результат несколько опережает цифирь 689.

[Pavlovsky]

А вот похоже секретное оружие лидеров конкурса.
http://tech.groups.yahoo.com/group/AlZi ... ssage/5071

Цитата:

If you do not look only at the end, but scan the whole sequence of the
top cards, you will see that long arithmetic sequences with difference
3 appear more often, but their appearance and length seem pretty
irregular. Permutations in the area of such sequences will have long
strings of the form ...,3,0,0,3,0,0,3,0,0,... - where I have listed
differences: CARD-POSITION. But it looks random: when this will
appear, how long is this pattern and whether it starts near the
beginning of the permutation or somewhere in the middle.

[dvorkin_sacha]

Pavlovsky

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

[Pavlovsky]

dvorkin_sacha
Для начала выполните все ваши обещания, которые вы щедро вдывали в этой ветке. А пока ваш статус: "неадекватный болтун". И все ваши посты не стоият времени потраченного на их чтение.

[Vitaly12]

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

dvorkin_sacha
Для начала выполните все ваши обещания, которые вы щедро вдывали в этой ветке. А пока ваш статус: "неадекватный болтун". И все ваши посты не стоият времени потраченного на их чтение.

К "неадекватный болтун" я бы еще добавил: "хамоватый"

[dvorkin_sacha]

Pavlovsky

это Вы "адекватное трепло", питающееся объедками с чужого стола, которое мне почему-то не хочется больше подкармливать: я и так достаточно конкретной информации уже выложил. А по поводу "хамоватого": не я первый начал.

Строгое предупреждение за хамство!

[Pavlovsky]

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

Pavlovsky

это Вы "адекватное трепло", питающееся объедками с чужого стола, которое мне почему-то не хочется больше подкармливать: я и так достаточно конкретной информации уже выложил. А по поводу "хамоватого": не я первый начал.

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

Строгое предупреждение за хамство!

[Nataly-Mak]

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

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

(Оффтоп)

16:

      130: 2 3 11 15 10 9 12 14 1 13 5 7 6 16 4 8 -> 1 3 2 4 5 6 7 8 9 10 11 
      12 13 14 15 16
      132: 2 3 11 13 8 15 1 4 5 16 10 14 6 9 7 12 -> 1 3 2 4 5 6 7 8 9 10 11 
      12 13 14 15 16
      133: 2 3 11 13 8 15 1 10 16 5 4 14 6 9 7 12 -> 1 3 2 4 5 6 7 8 9 10 11 
      12 13 14 15 16
      138: 2 6 14 8 1 11 12 9 13 5 7 4 15 16 10 3 -> 1 3 2 4 5 6 7 8 9 10 11 
      12 13 14 15 16

      19:

      180: 2 3 4 5 6 7 12 18 16 19 13 17 11 9 8 14 10 1 15 -> 1 13 12 11 10 6 
      5 4 2 3 7 8 9 14 15 16 17 18 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
  193: 2 3 4 5 10 8 19 13 11 7 6 16 9 18 14 12 1 17 15 -> 1 14 13 12 8 7 6 
  4 3 2 5 9 10 11 15 16 17 18 19
  196: 2 3 4 5 12 17 14 9 7 6 10 8 18 16 19 13 11 1 15 -> 1 13 12 11 10 6 
  5 4 2 3 7 8 9 14 15 16 17 18 19
  197: 2 3 4 6 9 5 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
  202: 2 3 4 6 10 8 9 5 12 17 14 7 18 16 19 13 11 1 15 -> 1 13 12 11 10 6 
  5 4 2 3 7 8 9 14 15 16 17 18 19
  202: 2 3 4 6 9 13 18 1 12 14 16 5 10 8 11 7 19 15 17 -> 1 16 15 14 13 12 
  11 10 6 3 4 9 2 5 8 7 17 18 19
  
  23:

  269: 2 3 4 5 6 7 8 9 12 11 10 14 20 18 16 1 22 19 13 15 23 17 21 -> 1 20 
  19 18 17 16 15 14 5 2 3 4 6 13 8 7 10 9 12 11 21 22 23
  275: 2 3 4 5 6 7 8 9 20 12 14 10 18 16 11 19 22 1 15 13 23 17 21 -> 1 20 
  19 18 17 14 15 16 13 12 11 10 4 3 2 5 6 7 8 9 21 22 23
  276: 2 3 4 5 6 7 8 9 20 11 16 1 22 19 18 12 10 13 15 14 23 17 21 -> 1 20 
  19 18 17 14 15 16 13 12 11 10 4 3 2 5 6 7 8 9 21 22 23
  276: 2 3 4 5 6 7 8 10 19 9 22 17 11 12 1 21 14 16 15 23 13 18 20 -> 1 19 
  18 17 16 15 8 10 6 5 7 3 2 9 4 11 12 13 14 20 21 22 23
  277: 2 3 4 5 6 7 8 10 15 9 13 1 21 23 19 17 11 22 12 18 14 16 20 -> 1 12 
  3 14 9 8 7 4 5 2 6 10 13 11 15 16 17 18 19 20 21 22 23
  293: 2 3 4 5 6 7 8 10 18 12 13 9 16 1 22 19 14 11 20 15 23 17 21 -> 1 20 
  19 18 17 14 15 16 13 12 11 10 4 3 2 5 6 7 8 9 21 22 23
  310: 2 3 4 5 6 7 8 10 13 16 22 17 14 11 9 15 12 1 21 18 23 19 20 -> 1 19 
  18 17 5 15 14 13 12 11 10 9 8 3 2 4 7 6 16 20 21 22 23
  
    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

      20:

      181: 2 3 4 5 6 7 8 11 18 1 13 20 16 19 10 9 14 17 12 15 -> 1 2 4 3 5 6 7 
      8 9 10 11 12 13 14 15 16 17 18 19 20
      191: 2 3 4 5 6 7 8 11 1 18 15 19 12 20 9 14 16 10 13 17 -> 1 16 15 14 8 
      7 6 4 3 2 5 9 10 11 12 13 17 18 19 20
      196: 2 3 4 5 6 7 8 12 16 19 10 9 1 17 11 14 13 20 18 15 -> 1 15 14 10 9 
      8 4 3 2 5 6 7 11 12 13 16 17 18 19 20
      196: 2 3 4 5 6 7 8 12 16 11 10 9 1 17 19 14 13 20 18 15 -> 1 15 14 10 9 
      8 4 3 2 5 6 7 11 12 13 16 17 18 19 20
      206: 2 3 4 5 6 7 9 18 11 13 8 14 10 12 19 1 20 17 16 15 -> 1 18 17 16 15 
      14 8 7 2 3 4 5 6 9 10 11 12 13 19 20
      216: 2 3 4 5 6 7 15 16 11 20 18 1 9 19 8 13 14 12 10 17 -> 1 9 8 5 4 3 2 
      6 7 10 11 12 13 14 15 16 17 18 19 20
      218: 2 3 4 5 6 8 16 13 20 12 10 1 18 19 11 7 15 9 14 17 -> 1 16 15 14 8 
      7 6 4 3 2 5 9 10 11 12 13 17 18 19 20
      225: 2 3 4 5 6 9 20 14 7 19 16 17 11 10 18 12 8 13 1 15 -> 1 13 12 11 2 
      9 8 7 10 3 6 5 4 14 15 16 17 18 19 20

      order 22

    227: 2 3 4 5 6 7 8 9 10 11 14 18 20 12 1 19 21 13 22 17 16 15 -> 1 16 15 
      14 3 12 6 5 2 7 4 11 8 13 10 9 17 18 19 20 21 22
      249: 2 3 4 5 6 7 8 9 10 13 1 15 17 21 12 14 18 19 11 22 16 20 -> 1 3 6 9 
      4 5 2 8 7 10 11 12 13 14 15 16 17 18 19 20 21 22
      258: 2 3 4 5 6 7 9 13 10 14 17 19 12 16 21 15 8 22 11 1 20 18 -> 1 17 16 
      15 11 10 9 5 2 3 4 6 7 8 12 13 14 18 19 20 21 22

      243: 2 3 4 5 6 7 9 13 10 18 1 15 17 19 14 12 21 11 8 22 16 20 -> 1 3 6 9 
      4 5 2 8 7 10 11 12 13 14 15 16 17 18 19 20 21 22
      256: 2 3 4 5 6 7 9 16 11 12 8 13 14 10 20 18 21 15 22 1 17 19 -> 1 4 3 2 
      5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

      248: 2 3 4 5 6 7 9 19 11 13 8 10 12 22 1 21 18 17 14 15 16 20 -> 1 19 18 
      17 13 12 11 7 6 5 2 3 4 8 9 10 14 15 16 20 21 22
      260: 2 3 4 5 6 7 9 14 13 12 10 17 11 8 20 21 19 22 16 15 1 18 -> 1 4 2 8 
      10 3 12 13 9 6 5 15 11 14 16 7 17 18 19 20 21 22

      order 21:

      209: 2 3 4 5 6 7 8 9 11 13 14 15 21 16 19 12 18 20 10 1 17 -> 1 15 14 13 
      12 4 5 6 7 3 2 8 9 10 11 16 17 18 19 20 21
      215: 2 3 4 5 6 7 8 9 18 20 15 21 19 17 12 11 10 16 13 1 14 -> 1 4 9 5 2 
      3 7 8 6 10 11 12 13 14 15 16 17 18 19 20 21
      221: 2 3 4 5 6 7 8 11 16 21 15 10 9 17 13 12 14 20 18 1 19 -> 1 16 15 14 
      10 9 8 4 3 2 5 6 7 11 12 13 17 18 19 20 21
      228: 2 3 4 5 6 7 8 13 14 11 16 10 9 18 12 1 20 17 21 15 19 -> 1 18 17 16
      15 12 13 14 11 10 9 8 3 4 2 5 6 7 19 20 21
      247: 2 3 4 5 6 7 9 10 13 12 16 21 15 17 8 11 14 20 18 1 19 -> 1 16 15 14 
      10 9 8 4 3 2 5 6 7 11 12 13 17 18 19 20 21

В последовательности для n=29 с результатом 689 взгляд на итоговую перестановку наводит на определённые мысли:

n=29: 8  3  4  14  11  16  18  7  21  9  15  20  22  5  12  6  10  2  25  27  17  13  26  28  1  29  19  24  23

Итоговая:

1  26  25  24  20  19  18  14  13  12  11  10  5  3  2  8  6  7  4  9  15  16  17  21  22  23  27  28  29

[dvorkin_sacha]

Nataly-Mak

Я уже писал, что для 689 все сводится к банальному наращиванию с вычислением всех (в хорошем алгоритме далеко не всех) перестановок 13! На втором этапе применяется "деревянный" алгоритм.

[Nataly-Mak]

(Оффтоп)

dvorkin_sacha
я ваши сообщения больше не читаю. В них слишком много оскорблений и необоснованных обвинений. Вы так и не сняли с меня ваше обвинение в том, что я включила в конкурс ваш результат для $n=19$, и не извинились за клевету.