Генерирование всех перестановок заданного множества

Напомним, что перестановкой n -элементного множества X называется упорядоченный набор длины n, составленный из попарно различных элементов множества X. Опишем некоторые методы генерирования последовательности всех n! перестановок n-элементного множества. Не нарушая общности будем рассматривать не исходное множество Х, а множество А= {1,2,… n } – множество индексов элементов, т.к. между множеством элементов из Х и множеством индексов из А существует взаимно однозначное соответствие, которое задается в виде: x_i «i.

Будем предполагать, что элементы множества запоминаются в виде элементов массива Р [1],…, Р [ n ]. Во всех методах элементарной операцией, которая применяется к массиву Р, является поэлементная транспозиция, т.е. обмен значениями переменных Р [ i ] и Р [ j ], где 1£ i, j £ n. Эту операцию будем обозначать Р [ i ]:=: Р [ j ]. Очевидно, что она эквивалентна последовательности команд: а:= Р [ i ]; Р [ i ]:= Р [ j ]; Р[ j ]:= а, где а – некоторая вспомогательная переменная.

Генерирование всех перестановок заданного множества в лексикографическом порядке

Данный метод легче всего понять, если в качестве переставляемых элементов взять числа 1,…, n. На множестве всех перестановок определим лексикографический порядок:

< x₁, x₂, …x_n > < < y₁, y₂, …,y_n > Û существует k ³1, такое что xk < yk и xp = yp для каждого p < k.

Заметим, что если вместо чисел 1,2,…, n взять буквы а, б,…, р с естественным порядком а < б < в <…< р, то лексикографический порядок определяет стандартную последовательность, в которой слова длины n появляются в словаре.

Для примера приведем перестановки множества X = {1,2,3} в лексикографическом порядке:

123, 132, 213, 231, 312, 321.

Начиная с перестановки (1,2,…, n), переход от текущей перестановки P =(p₁, p₂,…, p_n) к перестановке, следующей за текущей в смысле лексикографического порядка, осуществляется последовательным выполнением следующих действий:

1) просмотр Р справа налево в поисках самой правой позиции k, в которой p_k < p_k+1 (если такой позиции k нет, то текущая перестановка является последней и следует закончить генерацию);

2) просмотр P от p_k слева направо в поисках наименьшего из таких элементов p_m, что k < m и p_k < p_m; транспозиция элементов p_k и p_m и обращение отрезка p_k+1,…, p_n путем транспозиции симметрично расположенных элементов (заметим, что элементы обращаемого отрезка расположены в порядке убывания).

Например, для п =8 и Р =(2,6,5,8,7,4,3,1) имеем p_k =5 и p_m =7, результат транспозиции p_k и p_m - (2,6,7,8,5,4,3,1), результат обращения отрезка p_k+1,…, p_n переводит Р в перестановку (2,6,7,1,3,4,5,8), которая следует за Р в лексикографическом порядке.

Рекурсивный алгоритм генерирования всех перестановок заданного множества в лексикографическом порядке

Рассмотрим рекурсивный алгоритм генерирования перестановок в лексикографическом порядке. Заметим, что последовательность перестановок множества {1,2,…, n } в этом случае имеет следующие свойства, вытекающие непосредственно из определения: