Объем вычислительной работы будет значительно меньше, если порождать последовательность перестановок в порядке минимального изменения позиций элементов при переходе к каждой следующей перестановке. Для того, чтобы изменение было минимальным, любая перестановка должна отличаться от предыдущей транспозицией двух соседних (смежных) элементов. Например, следующие перестановки на множестве 3-х первых цифр римской системы счисления {I, V, X} отличаются транспозицией подчеркнутых смежных элементов:
Пт: (I) ; (V) ; (X) ; (I) ; (V) ; (VIX)
Транспозитивная последовательность легко выстраивается по следующему рекурсивному правилу. Пусть уже имеется последовательность (n-1)! перестановок из (n-1) элементов, в которой соседние перестановки отличаются транспозицией смежных элементов. Каждую из этих перестановок можно расширить до n-перестановки, добавляя элемент n на каждую позицию справа-налево для нечетных по номеру (n-1) перестановок и слева-направо для четных по номеру (n-1) перестановок. Порядок порождаемых таким образом перестановок для 3-х первых целых чисел показан на следующей диаграмме:
П3:(123)1 (132)2 (312)3 (321)4 (231)5 (213)6
- |-------------^------------------| |-----------------^----------------|
- справо-налево слева-направо
- П2:(12)1<-3 : добавить : 3-> (21)2
- нечетно четно
- |------------------------------^----------------------|
- П1(1)1 <-2: добавить справа-налево
- нечетно
Из этой диаграммы должно быть понятно, что сначала из тривиальной 1-ой перестановки (1) добавлением справа-налево элемента 2 порождается последовательность 2-перестановок П2, содержащая перестановки (12) и (21). Затем в них добавляется элемент 3, соответственно справа-налево, чтобы получить в итоге желаемую последовательность П3, которая состоит из следующих 3-перестановок:
П3:(1 2 3); (1 3 2); (3 1 2); (3 2 1); (2 3 1); (2 1 3).
Следует, однако, отметить, что рассмотренная рекурсивная схема транспозиции смежных элементов практически неэкономична, потому что приходится порождать целиком весь список последовательностей перестановок П12,...Пn из одного, из двух и, наконец, из n элементов, когда требуется получить только Пn. В связи с этим обстоятельством более привлекательным представляется итерационный вариант реализации алгоритма транспозиции смежных элементов. Для его описания удобно (как и раньше) ограничиться перестановками натуральных чисел от 1 до n.
Итерационный процесс алгоритма транспозиции элементов реализует последовательность позиционных смещений, когда один из элементов меняется местами со своим соседом слева или справа в зависимости от текущего направления смещения данного элемента. В результате такого смещения образуется очередная перестановка, которая отличается от предыдущей транспозицией 2-х смежных элементов. Следующий пример иллюстрирует технику транспозиции 2-х смежных элементов Pi и Pj при смещении элемента Pi вправо или элемента Pj влево, где направления смещения элементов условно обозначены стрелками:
(P1,... <=>,...Pn) => (P1, ...,,...Pn)
Для систематической организации итерационного процесса транспозиций на каждом шаге должны быть установлены направления смещения всех элементов и выбран смещаемый элемент. При этом для начального шага предъявляется лексиграфически наименьшая перестановка, где для всех элементов задано смещение влево, кроме элемента 1, который никогда сам не может быть смещен:
(P1=1, P2=, ...Pj=,...Pn=)
На каждой последующей итерации для смещения следует выбрать максимальный элемент, который больше своего соседа слева или справа в принятом направлении смещения:
Pm=maxPj|Pj-1< и j>1 или >Pj+1 и j<n
Это правило выбора смещаемого элемента можно сделать более удобным, если исключить проверку индексов граничных элементов и различие индексов соседей. Для этого нужно во-первых расширить перестановку слева и справа 2-мя фиктивными элементами P0 и Pn+1 с фиксированным значением (n+1). Это гарантирует автоматическое выполнение требуемых граничных условий:
n+1=P0> и < Pn+1=n+1
Во-вторых, целесообразно ввести функцию кодирования направлений, значения которой d(Pj) равны (-1) или (+1) в зависимости от текущих направлений смещения различных элементов перестановки:
d()=(-1) и d()(+1), а d(1)=0
Функция направлений может быть задана в форме вектора указанных значений для всех элементов перестановки и позволяет однозначно идентифицировать их соседей в направлении смещения по алгебраической сумме индексов:
j-1=j+d() или j+1=j+d()
С учетом рассмотренных алгебраических приемов правило выбора смещаемого элемента можно теперь записать в следующей форме, инвариантной относительно индексов и направлений смещения элементов:
Pm=maxPj>Pi, где i=j+d()
Выбранный по этому правилу элемент ??? меняется местами со своим соседом в направлении смещения, образуя очередную перестановку, в которой:
Pm<->Pi, где i=m+d(Pm)
После транспозиции нужно также изменить на противоположное направления смещения для всех элементов, которые больше выбранного:
d(Pj)<- -d(Pj) для всех Pj>Pm
Аналогичные итерации следует продолжать, пока не получена последняя перестановка, в которой невозможно смещение для всех элементов (Pm=1):
Pj<Pi, где i= j+ d(Pj) i, j=1...n
Любая эффективная алгоритмическая реализация рассмотренного итерационного процесса должна обеспечивать быстрый поиск транспозиций без полного перебора всех элементов перестановки. Эта информация может быть легко получена по обратной перестановке, где значения элементов идентифицируют позиции элементов прямой перестановки. Более точно, значение каждого элемента обратной перестановки показывает номер позиции, которую занимаем в прямой перестановке элемент, равный его индексу. При этом справедливо также двойственное утверждение: значение элементов прямой перестановки равны номерам позиций своих индексов в обратной перестановке. В частности, если Р и R обозначают, соответственно, прямую и обратную перестановки, то между значениями и позициями их элементов имеют место следующие формальные соотношения:
Rj=j <-> Pj=i
Например, пусть в обратной перестановке R4=1. Это значит, что в прямой перестановке 4 стоит в 1-ой позиции (P1=4). Наоборот, пусть в прямой перестановке P2=1, значит первый элемент обратной перестановки должен быть 2 (R1=2). В общем случае из этих соотношений непосредственно следует простой способ вычисления обратной перестановки по прямой, а также двойственное преобразование, которое восстанавливает прямую перестановку из обратной:
(P->R): RPj<- j-1,2...n или n ...2,1=i ->PRi: (P<-R)
В более наглядной форме эти преобразования можно представить следующей иллюстративной схемой. Сначала нужно поменять местами значение и индекс каждого элемента перестановки, а затем расположить элементы по позициям, в порядке из новых индексов. Эту схему обработки демонстрирует следующий пример взаимных преобразований следующей 4-перестановки, где для наглядности показаны индексы элементов:
P=(41 12 33 24) -> (14 21 33 42) ->(21 42 33 14)=R
P=(41 12 33 24) <- (12 24 33 41) <-(21 42 33 14)=R
В алгоритме транспозиции смежных элементов обратные перестановки R следует вычислять на каждой итерации, фиксируя текущие позиции элементов прямой перестановки Р. Имея такую информацию, смещаемый элемент легко найти путем просмотра обратной перестановки и, соответственно, значения элементов прямой перестановки. Просмотр нужно продолжать до выполнения условия транспозиции, которое в индексах обратной перестановки выглядит следующим образом:
T=PRT>PRT+ d(T) | T<i<PRi+d(i) и d(i)<- -d(i)
Аналогично рассмотренной выше схеме нужно поменять местами со своим соседом выбранный для смещения элемент (Т) в прямой перестановке, а также соответствующие их индексам элементы обратной перестановки RT и RT+d(T). Позиции указанных для транспозиции элементов можно найти, соответственно, по обратной и прямой перестановкам. В результате будет получена очередная пара перестановок, которые отличаются от предыдущей итерации транспозициями следующих элементов:
PRT<->PRT+d(T) и RS <-> RT, где S= PRT
Последовательность итераций рассмотренного алгоритма иллюстрирует следующий пример перечисления прямых и обратных 3-перестановок, где стрелки обозначают направления смещения элементов, а символы '^' и '~' указывают их транспозиции:
ПТ:( ) ) ; ( ); ( ) ; ( ) ; ( )
ПR: (1 ) ; ( ) ; ( 1) ; (3 ) ; ( 1 ) ; (2 1 3)