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

[dvorkin_sacha]

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

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

Кстати, более осмысленный алгоритм, использующий генерацию перестановок, разработал профессор Кнут, о чём мне писал svb, разобравшийся в этом алгоритме.

кхе-кхе ... до сих пор не разобрался.

С ходу эту программу не нашел: не подскажете ее адрес?

[svb]

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

С ходу эту программу не нашел: не подскажете ее адрес?

http://www-cs-faculty.stanford.edu/~uno/programs/topswops-fwd.w

[dvorkin_sacha]

svb

Спасибо.

[Nataly-Mak]

На форуме scilog.ru выложена программа:

Цитата:

procedure PERM(m:integer);
var i,j,c,k:integer;jj:longint;
b:byte;
begin
if (m=1) then begin
for i:=1 to np do
if p[i]<>1 then a[n+i]:=n+p[i]-1
else a[n+i]:=1;
a[1]:=n+p[np+1]-1;
aa:=a;
c:=0;
while aa[1]>1 do begin
jj:=aa[1];
inc(c);
asm
lea esi,aa
mov edi,esi
add edi,jj
dec edi
@n: mov al,ds:[esi]
xor al,[edi]
xor [edi],al
xor ds:[esi],al
inc esi
dec edi
cmp edi,esi
jg @n
end;
end;
if c>cm then begin cm:=c;am:=a;write(#13,cm,' ') end;
a[1]:=1;
end
else begin
i:=1;
repeat
PERM(m-1);
if (m mod 2 =0)and(m>2) then
if i<m-1 then j:=i
else j:=m-2
else j:=m-1;
if (m=np+1) and (p[j]=1) then begin
b:=p[m-1];for k:=m-1 downto 2 do p[k]:=p[k-1];p[1]:=b;
inc(i)
end;
b:=p[m];p[m]:=p[j];p[j]:=b;
inc(i);
until i>m-1;
PERM(m-1);
end;
end;

Может быть, кому-нибудь пригодится.
За пояснениями, наверное, можно обратиться к автору программы svb.
Предполагаю, что в программе выполняется генерация перестановок. Автор только сообщил, что в основе программы лежит алгоритм В. Липского.

Я пока ещё работаю с помощью своего алгоритма наращивания последовательностей, его возможности не исчерпала до конца, ибо улучшения пока получаются. Но трудно выполнять добавление 11 и 12 карт в том смысле, что это выполняется долго в отличие от добавления меньшего количества карт.

[Pavlovsky]

Вот еще побочная задачка.

Доказать что рекордная перестановка не может заканчиваться числом 1. Для всех порядков n>2.

[Nataly-Mak]

По ходу работы я составляю базу данных - максимальные последовательности для всех $n$, даже для тех, которые не входят в конкурсную задачу, потому что они мне нужны для всевозможных переходов.

Так вот в этой БД сначала всё идёт очень хорошо: количество шагов как функция количества карт в колоде монотонно возрастает:

n=2: 1
n=3: 2 (+1)
n=4: 4 (+2)
n=5: 7 (+3)
n=6: 10 (+3)
n=7: 16 (+6)
n=8: 22 (+6)
n=9: 30 (+8)
n=10: 38 (+8)
n=11: 51 (+13)
n=12: 65 (+14)
n=13: 80: (+15)
n=14: 101 (+21)
n=15: 113 (+12)
n=16: 139 (+26)
n=17: 159 (+20)
n=18: 191 (+32)
. . . . . . . . . . . .

А вот дальше у меня такого монотонного возрастания не наблюдается.
Например:

n=30: 620
n=31: 698 (+78)
n=32: 713 (+15)
n=33: 778 (+65)
n=34: 788 (+10)
n=35: 951 (+163)
n=36: 955 (+4)
n=37: 1043 (+88)
n=38: 1097 (+54)
. . . . . . . . . .

Возрастание, конечно, имеется везде, но оно идёт как-то рывками: то слишком много, то слишком мало.
Отсюда делаю вывод, что многие максимальные последовательности у меня далеки от истинных.

[Nataly-Mak]

Да, значит, все уже всё решили
Одна я всё мучаюсь

Провела эксперимент, может быть, будет кому-то полезен.
Раньше я была уверена, что при наращивании последовательностей большее прибавление шагов даёт последовательность, не приводящая к тождественной перестановке. Из проведённого эксперимента видно, что это не всегда так.
Буду называть последовательность, приводящую к тождественной перестановке, последовательностью типа А, а не приводящую к тождественной перестановке - последовательностью типа B. Прибавление шагов при наращиваниии последовательностей обозначим P.
В эксперименте добавляю ко всем последовательностям 10 карт, то есть делается переход от последовательности из $n$ карт к последовательности из $n+10$ карт.

Результаты эксперимента:

n=16
тип А (130 шагов): P=281
тип B (139 шагов): P=280
n=17
тип А (159 шагов): P=274
тип B (159 шагов): P=283
n=18
тип А (191 шаг): P=297
тип B - нет последовательности с числом шагов больше 191
n=19
тип А (? мне неизвестно): P=340
тип B (221 шаг): P=317
n=20
тип А (224 шага): P=348
тип B (249 шагов): P=366
n=21
тип А (255 шагов): P=381
тип B (269 шагов): P=414
n=22
тип А (? мне неизвестно): P=412
тип B (288 шагов): P=392

Прошу восполнить пробелы в данных эксперимента, если у кого-то эти данные есть. Для n=19 и n=22 нужны не сами последовательности, приводящие к тождественной перестановке, а число шагов, которое они дают.

Для $n=18$ интересно узнать, получил ли кто-нибудь последовательность с числом шагов больше 191, конечно, не приводящую к тождественной перестановке; максимальная последовательность типа А уже получена и она даёт 191 шаг.
Если не жалко, можно и саму последовательность привести, ибо она не входит в конкурсную задачу. То же относится и к последовательностям для n=22 обоих типов.

Далее, наверное, ещё не факт, что результат 221 яляется максимумом для $n=19$, а результат 249 - максимум для $n=20$. Есть ли у кого результаты больше указанных? Интересно знать рекорды.

В нашей команде на сегодня максимумы такие (привожу до $n=30$):

19 221
20 249
21 269
22 288
23 331
24 348
25 372
26 436
27 470
28 493
29 597
30 620

Если интересно, могу все максимумы выложить.

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

[Pavlovsky]

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

Вот еще побочная задачка.

Доказать что рекордная перестановка не может заканчиваться числом 1. Для всех порядков n>2.

Пусть у нас есть перестановка P порядка n, которая заканчивается на 1 и количество инверсий (ходов) равно F(P). Удалим из перестановки 1, а число n заменим на 1. Тогда мы получим перестановку P' порядка n-1. Количество инверсий (ходов) которой равно F(P)-1.

То есть исходную задачу можно переформулировать так:
Пусть F(n) рекордное количество ходов для перестановок порядка n. Доказать что F(n+1)-F(n)>1 для всех n>2.

К тому же приводит и следующая задача

Доказать что рекордная перестановка порядка n не может ничинаться числом n.

[Nataly-Mak]

Я сообщала уже о программе svb, которая ищет последовательности, приводящие к тождественной перестановке.
Опрбовала эту программу давно ещё (сразу же, как он мне её прислал), получила последовательность для $n=15$, приводящую к тождественной перестановке. Для следующих $n$ не стала ждать, уже долго программа выполняется.

А вчера решила попробовать, будет ли программа работать, если в качестве итоговой задать не тождественную перестановку, а какую-то другую последовательность.
Задала итоговую последовательность для $n=12$:

1 6 5 2 3 4 7 8 9 10 11 12

Программа очень быстро отработала и выдала исходную последовательность:

2 6 1 10 11 8 12 3 4 7 9 5

65 шагов.

Вот такая отличная программа! Жаль только, что для больших $n$ она очень долго работает. Испытания для $n=23$ у меня ничем не закончились, просто прервала программу.

[Nataly-Mak]

В OEIS появилась последовательность для $n=19$, приводящая к тождественной перестановке (A000376), она даёт 207 шагов.
Таким образом, для $n=19$ тоже верно, что последовательность типа А даёт не больше шагов, чем последовательность типа B.

dvorkin_sacha
почему бы вам не отправить в OEIS свои максимальные последовательности для $n=20, 21, 22, 23$, приводящие к тождественной перестановке, коль скоро вы уверены, что они действительно максимальные?

[dvorkin_sacha]

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

В OEIS появилась последовательность для $n=19$, приводящая к тождественной перестановке (A000376)

А где там написано о тождественной перестановке?
Да, по поводу $n = 23$ я скорее всего был неправ: у меня число перекладывний практически совпадает с приводимым Вами максимальным результатом: 384. Для $n = 19$ у меня максимальное число перекладываний > $220$.

[Nataly-Mak]

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

Цитата:

For n=17, (2 10 15 11 7 14 5 16 6 4 17 13 1 3 8 9 12) is the only longest-winded permutation (or order of cards) that takes 159 steps of "topswopping moves" before it terminates in sorted order, i.e. (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17)

[Nataly-Mak]

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

Для $n = 19$ у меня максимальное число перекладываний > $220$.

Не поняла. Для какой последовательности у вас для $n=19$ число шагов $>220$? Для такой, которая оканчивается тождественной перестановкой? Тогда у вас результат больше, чем указан в OEIS (ибо там всего 207 шагов).

Если же вы имеете в виду последовательность типа B (не приводящую к тождественной перестановке), тогда понятно. Уже давно многие на конкурсе нашли результат для такой последовательности 221 шаг. Но не факт, что это максимум.

[dvorkin_sacha]

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

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

Для $n = 19$ у меня максимальное число перекладываний > $220$.

Не поняла. Для какой последовательности у вас для $n=19$ число шагов $>220$? Для такой, которая оканчивается тождественной перестановкой? Тогда у вас результат больше, чем указан в OEIS (ибо там всего 207 шагов).

Если же вы имеете в виду последовательность типа B (не приводящую к тождественной перестановке), тогда понятно. Уже давно многие на конкурсе нашли результат для такой последовательности 221 шаг. Но не факт, что это максимум.

Для $n=19$ имеются 2 решения с 207 шагами. Но это результат тривиальный. А вот для $n=23$ полученное мною решение, практически совпадающее с тем максимальным, которое Вы приводили, заслуживает внимания: дело в том, что для последовательности, к которой оно приводит, результат является максимальным, т.е. его невозможно уже улучшить. Думаю, что ценители нетривиальных результатов смогут это должным образом оценить (число перекладываний почти 400!).

[dvorkin_sacha]

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

Для $n=19$ имеются 2 решения с 207 шагами. Но это результат тривиальный...

Разумеется, речь идет о шагах, приводящих к тождественной перестановке. Для получения этого результата не надо быть героем (я эти решения получил за считанные секунды). Для общего случая таких решений - куча.