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

[Pavlovsky]

Чего то торкнуло. Самой трудоемкой процедурой в основе любого алгоритма по заданной теме является процедура инверсии.
Полагаю все эту процедуру реализовали примерно так:

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

А можно ли придумать такую структуру данных для хранения перестановки, чтобы операция инверсии выполнялась значительно быстрее?!

[dvorkin_sacha]

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

А можно ли придумать такую структуру данных для хранения перестановки, чтобы операция инверсии выполнялась значительно быстрее?!

Можно, но решение вопроса лежит в другой плоскости.

[Nataly-Mak]

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

Чего то торкнуло. Самой трудоемкой процедурой в основе любого алгоритма по заданной теме является процедура инверсии.
Полагаю все эту процедуру реализовали примерно так:

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

Насколько понимаю, в приведённой реализации каждый элемент отдельно переобозначается через некоторую переменную b.
Это в самом деле долго.
У меня не так. Я сразу записываю все элементы, подлежащие инверсии во вспомогательный массив $c(i)$, а затем просто переписываю этот массив в обратном порядке и получаю готовую инверсию $a(i)$.
В моих программах эта процедура не является самой трудоёмкой. Например, я генерировала по 100000 комбинаций (при наращивании последовательностей со случайной генерацией), эти комбинации проверяются на количество перекладываний за несколько секунд, генерация выполняется дольше.

[dvorkin_sacha]

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

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

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

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

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

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

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

И еще несколько уточнений: я писал про число шагов более $>220$, т.к. Вы указывли цифирь 220, и не более того. Что касается решения с числом перекладываний $221$, то оно получается элементарно: сначала каким-либо методом (например, одним из методов наращивания последовательностей, у которых уже давно борода отросла), находите решение с достаточно высоким числом перекладываний (их классифицировать можно по получаемым в результате перекладываний корням, т.к. их будет значительно меньше, чем предварительных решений) и далее, отступая подальше от листа дерева, применяете "деревянный" алгоритм. Т.к. я не принимаю участие в конкурсе, то привожу мои конкретные цифры. Предварительное решение со $179$ перекладываниями (одно уточнение: в случае применения методов наращивания не надо никаких наращиваний делать!):

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

А вот уточненные решения с $221$ перекладываниями (аж пять штук, полученные мною за доли секуды):

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

Конечно, техника работы, как в случае спуска, так и подъема по дереву решения, должна быть достаточно высока.

[Vitaly12]

Цитата:

применяете "деревянный" алгоритм

Вы имеете ввиду поочередную инверсию по элементам, которые находятся на "своих" местах (т.е. напр. карта с номером 5 - на пятом месте)?

-- Чт янв 13, 2011 16:28:51 --

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

Чего то торкнуло. Самой трудоемкой процедурой в основе любого алгоритма по заданной теме является процедура инверсии.
Полагаю все эту процедуру реализовали примерно так:

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

А можно ли придумать такую структуру данных для хранения перестановки, чтобы операция инверсии выполнялась значительно быстрее?!

Linked list - для инверсии лишь меняются местами "голова" и "хвост" - в форуме
Зиммерманна есть ссылка на описание этой процедуры.

[dvorkin_sacha]

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

Цитата:

применяете "деревянный" алгоритм

Вы имеете ввиду поочередную инверсию по элементам, которые находятся на "своих" местах (т.е. напр. карта с номером 5 - на пятом месте)?

Примерно так, но если Вы ознакомитесь с моим сообщением по поводу n = 23, то с трудом в это поверите, а если точней, то совсем не поверите. Так что есть над чем порассуждать. И еще посмотрите на начальное приближение, полученное, в моем предыдущем сообщении: очевидно, что пришлось работать с 16! (факториал от 16). В это тоже очень трудно поверить, но это так (о чем и говорит результат). Но уж такова моя судьба сродни судьбе барона Мюнхаузена.

[Nataly-Mak]

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

А вот уточненные решения с $221$ перекладываниями (аж пять штук, полученные мною за доли секуды):

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

Не вижу, чем отличаются эти две последовательности одна от другой
По-моему, они совершенно одинаковые. Или я что-то не понимаю?

[Vitaly12]

[quote=И еще посмотрите на начальное приближение, полученное, в моем предыдущем сообщении: очевидно, что пришлось работать с 16! (факториал от 16). [/quote]

16! = 20922789888000
Что Вы имели ввиду? Вы ведь не хотите сказать, что перебрали ВСЕ возможные случаи случаи?!

[dvorkin_sacha]

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

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

А вот уточненные решения с $221$ перекладываниями (аж пять штук, полученные мною за доли секуды):

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

Не вижу, чем отличаются эти две последовательности одна от другой
По-моему, они совершенно одинаковые. Или я что-то не понимаю?

Все правильно понимаете: в конце расчета первый максимальный результат дублируется, вот я его по рассеянности и присоседил - ведь расчет производился давно и многое подзабылось.

-- Пт янв 14, 2011 00:11:03 --

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

Что Вы имели ввиду? Вы ведь не хотите сказать, что перебрали ВСЕ возможные случаи?!

Я имею в виду то, что мой алгоритм учитывает все случаи, в которых последовательность можно считать кандидатом для дальнейшего рассмотрения. Но, вообще говоря, результат (в смысле его максимальности) для n = 23 выглядит еще более фантастическим.

[Vitaly12]

[quote=Но, вообще говоря, результат (в смысле его максимальности) для n = 23 выглядит еще более фантастическим.[/quote]
Безусловно, но не совсем понятно, как Вы определяете приближенность результата к максимальному.

[quote=мой алгоритм учитывает все случаи, в которых последовательность можно считать кандидатом для дальнейшего рассмотрения.[/quote]
Вы имеете ввиду, что ваш алгоритм отсекает целые ветви, не проходя их поначалу? Если да, то по какому критерию?

[dvorkin_sacha]

Vitaly12

Я просто доказываю, что результат для сгенерируемой мною последовательности максимален (т.е. если в результате n перекладываний мы получаем впереди единицу, то для этой самой последовательности впереди с единицей не существует первоначальной последовательности, из которой она получена, с большим числом перекладываний). Об остальном умолчу.

[Pavlovsky]

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

Linked list - для инверсии лишь меняются местами "голова" и "хвост" - в форуме
Зиммерманна есть ссылка на описание этой процедуры.

А можете дать прямо ссылку. Я думал над связанными списками, но ничего хорошего не придумал. Поменять голову и хвост этого мало.

А так же если не трудно, расскажите где находится форум Зиммермана. Вы имеете ввиду дискуссионные группы?! В прошлый раз попытался в них зарегистрироваться, но у меня не получилось.

[Vitaly12]

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

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

Linked list - для инверсии лишь меняются местами "голова" и "хвост" - в форуме
Зиммерманна есть ссылка на описание этой процедуры.

А можете дать прямо ссылку. Я думал над связанными списками, но ничего хорошего не придумал. Поменять голову и хвост этого мало.

А так же если не трудно, расскажите где находится форум Зиммермана. Вы имеете ввиду дискуссионные группы?! В прошлый раз попытался в них зарегистрироваться, но у меня не получилось.

Нужно зарегистрироваться, а потом поискать в сообщениях ближе к началу текущего конкурса.
tech.groups.yahoo.com/group/AlZimmermannsProgrammingContests

[Pavlovsky]

Со второй попытки сумел зарегитьс в группе.
Нашел такую ссылку. http://tomas.rokicki.com/pancake/ по ссылке такой текст:

Цитата:

The normal representation is to use an array where a[i] contains the size of the pancake at position i. With the add trick, the pancake stack is instead represented as a doubly-linked list using an array b[], where b[i] contains the *sum* of the preceding and succeeding pancakes. In addition, you need to remember the first pancake somewhere.

Why is this a cool representation? Consider a flip. In the normal representation, for a flip of m pancakes, you need to modify all the elements of a[i] for 0<=i<m; no matter how you do this, it's going to be slow. But in the new representation, if you know which pancake is at position m (call this p), at position m-1 (call this prev), and at the beginning (first), all you need to do to "flip" it is:

b[first] += p ;
b[prev] -= p ;
b[p] += first - prev ;
because what's happening is the pancake at "first" is gaining a neighbor (p), the pancake at prev is losing a neighbor (p), and the pancake at p is having a neighbor changed from prev to first. The key is that the information associated with pancakes on the interior of the flip does not change during the flip; the neighbors of those pancakes (and thus their sum) remains the same. To walk the entire stack from front to back, we do something like:

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

Я так понимаю это и есть алгоритм инверсии, но вот врубиться в алгоритм пока не могу.

[Vitaly12]

[quote=Я так понимаю это и есть алгоритм инверсии, но вот врубиться в алгоритм пока не могу.[/quote]
Это и есть алгоритм и он работает, правда общий выигрыш во времени не в разы