Алгоритмы порождения перестановок

Также как и при генерации сочетания будем считать, что элементами множества являются целые числа от 1 до n.

Последовательность перестановок на множестве {1,2,..., n } представлена в лексикографическом порядке, если она записана в порядке возрастания получающихся чисел. Например, лексикографическая последовательность перестановок трех элементов имеет вид 123, 132, 213, 231, 312, 321.

Порождать такую последовательность можно следующим образом. Начиная с перестановки Р =(1,2,..., n), переходим к следующей, путем просмотра текущей справа налево с целью поиска самой правой позиции, в которой р_i < р_{i +1}. Найдя ее, ищем р_j, наименьший элемент, расположенный справа от р_i и больше его. Затем осуществляется транспозиция элементов р_i и p_j и отрезок р_{i +1},..., р_n (элементы которого расположены в порядке убывания) переворачивается. Например, для n =8 имеем текущую перестановку p =(2,6,5,8,7,4,3,1), тогда р_i =5 (i =3) и р_j =7 (j =5). Меняя их местами и переворачивая p ₄, p ₅, p ₆, p ₇, p ₈, получаем следующую перестановку (2,6,7,1,3,4,5,8). Эту процедуру реализует алгоритм представленный на рис.2.8.

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

Такую последовательность перестановок можно построить рекурсивно. Для n =1 существует единственная перестановка (1). Предположим, что построена последовательность перестановок П₁,П₂,...,П_{( n -1)!} на множестве {1,2,..., n -1} в порядке минимального изменения.

Расширим каждую из (n -1)! этих перестановок путем вставки элемента n на каждое из n возможных мест. Причем, элемент n добавляется к П _i последовательно во все позиции справа налево, если i нечетное, и слева направо, если i четное. Пример такого расширения представлен на рис.2.9.

Эту же последовательность перестановок можно порождать итеративно, получая каждую перестановку из предшествующей и добавочной информации. Это делается с помощью трех векторов: текущей перестановки Р =(р ₁,..., р_n), обратной к ней перестановки 0 =(о ₁,..., о_n) (о ₁ - индекс наименьшего элемента в Р, о ₂ - индекс следующего по величине элемента в Р и т.д., следовательно, ) и записи направления D =(d ₁,..., d_n), в котором сдвигаются элементы перестановки (d_i =-1, если p_i сдвигается влево, d_i =1 - вправо, d_i =0 - не сдвигается). Элемент сдвигается до тех пор, пока не достигнет элемента большего чем он сам; в этом случае сдвиг прекращается. В этот момент направление сдвига данного элемента изменяется на противоположное и передвигается следующий меньший его элемент, который можно сдвинуть. Поскольку хранится перестановка, обратная к Р, то в Р легко найти место следующего меньшего элемента. Эту процедуру реализует алгоритм представленный на рис.2.10.

Заметим, что в данном алгоритме Р ₀ и P_{n +1} инициализируются величиной n +1, чтобы прекратить передвижение n, и d ₁ инициализируется нулем, чтобы в тех случаях, когда m становятся равным единице во внутреннем цикле, остаток внешнего цикла был правильно определен.

Алгоритм порождения случайных перестановок представлен на рис.2.11. Данный алгоритм аналогичен алгоритму порождения случайных сочетаний (рис.2.7).