nextupprevious

Next:4.12 Порождение подмножеств множества
Up:4 Разработка алгоритмов
Previous:4.10 Методы порождения объектов

4.11 Порождение перестановок

Рассматривая задачу порождения $n!$ перестановок множества элементов $a_1,\ldots,a_n$, без ограничения общности будем полагать, что для любого $i$ выполняется $a_i=i$, т.е. элементами множества являются целые числа от 1 до $n$. Такое упрощение возможно (и будет использоваться) и для других рассматриваемых здесь комбинаторных объектов, таких, как подмножества и сочетания.

Прямое применение алгоритма поиска с возвращением к перестановкам порождает их в лексикографическом порядке, т.е. получаемая последовательность для $n=3$ имеет вид (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Их также можно порождать следующим алгоритмом.

Начинаем с перестановки $(1,2,\ldots,n)$, а переход от текущей перестановки $\Pi = (\pi_1, \pi_2,\ldots, \pi_n)$ к перестановке, следующей за текущей в смысле лексикографического порядка, осуществляем последовательным выполнением следующих действий:

1) просмотр $\Pi$ справа налево в поисках самой правой позиции $i$, в которой $\pi_i < \pi_{i+1}$ (если такой позиции $i$ нет, то текущая перестановка является последней и следует закончить порождение);

2) просмотр $\Pi$ от $\pi_i$ слева направо в поисках наименьшего из таких элементов $\pi_j$, что $i<j$ и $\pi_i <\pi_j$;

3) транспозиция (взаимная замена) элементов $\pi_i$ и $\pi_j$ и обращение отрезка $\pi_{i+1},\ldots, \pi_n$ путем транспозиции симметрично расположенных элементов (заметим, что элементы обращаемого отрезка расположены в порядке убывания).

Например, для $n=8$ и $\Pi = (2,6,5,8,7,4,3,1)$ после выполнения первых двух шагов имеем $\pi_i =5$ и $ \pi_j = 7$, а результат транспозиции $\pi_i$ и $\pi_j$ и обращения отрезка $\pi_{i+1},\ldots, \pi_8$ переводит $\Pi$ в (2,6,7,1,3,4,5,8).

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

Важность лексикографического порядка определяется его простотой и естественностью. Существенным недостатком его следует признать сравнительно большой объем той работы, которую необходимо выполнить для преобразования текущего объекта в объект, являющийся следующим в смысле лексикографического упорядочения. Например, при $n=3$ соседними являются перестановки (2,3,1) и (3,1,2), различающиеся во всех позициях. При порождении комбинаторных объектов (в частности, перестановок) стремятся использовать такое их упорядочение, при котором следующий объект строится по предыдущему наиболее просто. Для многих классов комбинаторных объектов удается найти так называемый порядок минимального изменения, минимизирующий объемы работы по переходу от текущего элемента к соседнему и, таким образом, приводящий к наилучшим временным характеристикам алгоритма порождения комбинаторных объектов данного класса.

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

Можно дать простое рекурсивное описание для процесса построения перестановок в таком порядке. Для $n=1$ единственная перестановка (1) удовлетворяет нашим требованиям. Если $n>1$, то из последовательности перестановок $\Pi_1,\Pi_2,\ldots, \Pi_r$ для множества $1,2,\ldots, n-1$ строится последовательность перестановок для $n$ элементов за счет расширения каждой из $(n-1)!$ перестановок $\Pi_i$ вставкой элемента $n$ на каждое из $n$ возможных мест ("промежутков" между элементами $\Pi_i$), справа налево при нечетном $i$ или слева направо при четном $i$.

Однако с точки зрения объема памяти, необходимого для выполнения описанного процесса, порождать всю последовательность целиком нецелесообразно. В этом смысле более предпочтительным оказывается итеративное порождение элементов той последовательности, когда каждая следующая перестановка получается из предыдущей с использованием дополнительно хранимой и небольшой по объему вспомогательной информации. В приведенном ниже алгоритме, который порождает перестановки в порядке минимального изменения, такой вспомогательной информацией служит перестановка $Q=(\phi_1, \phi_2, \ldots, \phi_n)$ обратная к текущей $\Pi = (\pi_1, \pi_2,\ldots, \pi_n)$ (т.е. такая, что $\phi_{\pi_i} = i$ для всех $i, 1 \leq i \leq n$), а также "вектор направлений" $D = (d_1,\ldots, d_n)$, в каждом элементе которого хранится направление $d_i$ сдвига числа $i$.

for all $i$ from [1, $n$] do
      $\pi_i := i; \phi_i := i; d_i := -1$
end;
$d_i := 0; \pi_o := n + 1; \pi_{n+1} := n + 1;m := n + 1;$
while $m$ # 1 do
    Вывести текущее значение $\Pi = (\pi_1, \pi_2,\ldots, \pi_n)$; $m := n$;
    while$\pi_{\phi_m + d_m} > m$do $d_m := - d_m; m := m - 1$end;
    Осуществить транспозицию элементов $\pi_{\phi_m}$ и $\pi_{\phi_m + d_m}$ в $\Pi$;
    Осуществить транспозицию элементов $\phi_m$ и $\phi_{\pi_{\phi_m}}$ в Q
end.

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

Корректность алгоритма можно доказать индукцией по $n$, используя следующее свойство вектора направлений.

В момент порождения текущей перестановки $\Pi = (\pi_1,\ldots, \pi_n)$ значения $d_i$ для $i$, $1 \leq i \leq n$, совпадают с соответствующими значениями $d_i$ в тот момент, когда во время порождения всех перестановок множества $\{ 1,2,\ldots, n-1 \}$ этот алгоритм порождает перестановку $\Pi'$, которая отличается от $\Pi$ только тем, что в $\Pi'$ нет числа $n$. Это свойство вектора направлений в свою очередь можно доказать индукцией по числу уже порожденных перестановок для $ \{1,2,\ldots, n \}$.

Next:4.12 Порождение подмножеств множества
Up:4 Разработка алгоритмов
Previous:4.10 Методы порождения объектов

© В.Н. Касьянов,Е.В.Касьянова, 2004