topswops

12 февраля завершен очередной конкурс Зиммермана. Окончательный рейтинг участников можно посмотреть здесь.

Постановка задачи

Имеется стопка из n карт. На каждой карте число от 1 до n. Пусть, например, на верхней карте число k. Перекладываем в обратном порядке верхние k карт. Эту операцию выполняем до тех пор, пока сверху не появится единица. Например, для 6-ти карт с исходной перестановкой

365142

можно выполнить следующие операции:

365142
563142
413652
631452
254136
524136
314256
413256
231456
321456
123456

Итого десять операций.

Задача. Получить начальную расстановку карт с максимальным числом операций. Нужно решить эту задачу для 25-ти значений n - простых чисел, меньших сотни (2, 3, 5, … 97).

Техника перебора

В [1] вводится понятие фронта последовательности - это последовательность первых элементов из каждой последовательности при выполнении операций. Для примера выше это последовательность

35462

Используя это определение, перебор вариантов можно выполнять следующим способом.

Начальная последовательность - номера позиций со знаком минус (от 1 до заданного количества карт k):

-1-2-3-k

Дополнительно хранится массив с еще не использованными картами. На каждом шаге выполняем следующую последовательность действий:

На первую позицию текущей последовательности ставим по очереди еще не использованные карты. Число в первой позиции последовательности дает нам позицию карты в исходной последовательности (чтобы не восстанавливать последовательность по ее фронту в самом конце). Для каждой поставленной карты делаем реверс, пока возможно.

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

До n=16 еще реально сделать полный перебор последовательностей таким способом. Причем последовательности с максимальным числом операций появляются в самом начале такого перебора. Так что и для n=17 максимальную последовательность можно найти этим же спосбом.

Реверс массива

Основной операцией в описанном выше переборе является операция изменения порядка следования элементов массива на обратный. Самый простой способ выполнения этой операции:

pascal
   m := p;
   for j := 1 to m div 2 do begin
      t := a[j];
      a[j] := a[m-j+1];
      a[m-j+1] := t;
   end;

Примерно на 20% можно ускорить эту операцию, если применить SIMD-инструкции. В коде ниже метод revers_fast() выполняет реверс первых p элементов байтового массива a .

Еще один интересный способ реверса описан здесь. Используется двусвязный список, в котором обе ссылки (прямая A и обратная B) хранятся как (A xor B). Тогда зная ссылку A нетрудно получить B и наоборот. В качестве ссылок можно взять индексы элементов массива.

Таблица последовательностей

Последовательности, полученные мной (5-е место в рейтинге). В силу специфики используемого алгоритма приходилось искать последовательности и для составных значений n .

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

Источники

1Linda Morales. A Quadratic Lower Bound for Reverse Card Shuffler
4Within Every Math Problem, For this Mathematician, Lurks a Card-Shuffling Problem By Erica Klarreich
5Problems in applied mathematics: selections from SIAM review Авторы: Murray S. Klamkin
6Problem 76-17. A Reverse Card Shuffle

12 февраля 2011

No comments
Вы можете оставить комментарий или задать вопрос
Ваше имя:

Текст сообщения:


Copyright © 2009-2014 by