1.3. Генерация перестановок
1.3.1. Генерация перестановок в лексикографическом порядке
Будем рассматривать
исходное множество
,
и в качестве начальной перестановки
возьмем
.
Условие окончания работы — порождение
перестановки
,
которая является последней в
лексикографическом смысле среди всех
перестановок множества X.
Переход от текущей перестановки
к следующей за ней будем осуществлять
таким образом:
1) просматривая
перестановку
справа налево, ищем самую первую позицию
i
такую, что
(если такой позиции нет, значит текущая
подстановка
и процесс генерации завершается);
2) просматривая
от
слева направо, ищем наименьший из
элементов
такой, что
;
3) меняем местами
элементы
и
;
затем все элементы
записываем в обратном порядке (т.е.
меняем местами симметрично расположенные
элементы
и
).
Пример.
Пусть текущая перестановка
имеет вид
.
На первом шаге найдены
;
на втором —
;
на третьем шаге меняем местами
и
:
(3, 6, 7, 5, 4, 2, 1) и меняем местами элементы,
начиная с третьей позиции: (3, 6, 1, 2, 4, 5,
7) — получили подстановку, следующую за
текущей в лексикографическом порядке.
1.3.2. Генерация перестановок с помощью вложенных циклов
Будем говорить,
что перестановка
является циклом длины k
степени d,
если ее элементы
,
получены из 1, 2, … , k
циклическим сдвигом вправо на d
позиций, остальные n
– k
элементов
стационарны. Например, подстановка
является циклом длины 4 степени 1.
Алгоритм порождения подстановок с помощью вложенных циклов основан на следующей теореме.
Теорема 1. Любую подстановку на множестве можно представить в виде композиции
(1.2)
где
— циклическая подстановка порядка i.
Пример.
Представим в виде (2.1) подстановку
,
т.е. запишем
.
Очевидно, последний
цикл является тождественной подстановкой.
Определим
:
т.к.
то
следовательно
— цикл порядка 4.
Т.к.
,
то
и
.
Разложение подстановки имеет вид:
(1.3)
Д
иаграмма
композиции (1.3) приведена на рис. 2.2.
Из теоремы 1 следует,
что все перестановки можно получить
систематическим перебором циклических
сдвигов. В качестве начальной перестановки
берем
и сдвигаем на одну позицию вправо все
элементы до тех пор, пока вновь не получим
;
теперь сдвигаем циклически первые
элементов и снова повторяем сдвиг всех
n
элементов на одну позицию до тех пор,
пока не получим уже имеющуюся перестановку;
сдвигаем циклически ее первые
элементов… и т.д., пока не переберем все
перестановок. Ниже приведен алгоритм
вложенных циклов.
1. Цикл (
)
1.1.
;
2. Конец цикла
3.
4. Пока (
)
4.1.Печать
4.2.
4.3. Сдвиг первых k элементов на одну позицию
4.4. Пока (
и
)
4.4.1.
4.4.2. Сдвиг первых k элементов на одну позицию
4.5. Конец цикла
5. Конец цикла
6. Конец
Этот алгоритм не является эффективным, т.к. на каждом шаге требует большого количества (не меньше n) транспозиций (транспозиция — обмен местами двух элементов).
1.3.3. Транспозиция соседних элементов
Описанные выше алгоритмы генерации перестановок не являются алгоритмами с минимальными изменениями. Минимальным изменением при переходе от текущей перестановки к следующей является транспозиция двух элементов. Дадим рекурсивное описание такого алгоритма.
Если
,
то существует единственная перестановка
.
Пусть
и последовательность перестановок
на множестве
построена. Для получения перестановок
на множестве
будем вставлять элемент n
на «промежутке» между элементами
перестановки
по следующему правилу: если номер i
подстановки
— нечетное число, то элемент n
вставляется в промежутки справа налево,
если I
— четное число, то элемент n
вставляется в промежутки между элементами
слева направо.
Пример генерации
перестановки при
приведен на рис. 1.3.
