Объем вычислительной работы будет значительно меньше, если порождать последовательность перестановок в порядке минимального изменения позиций элементов при переходе к каждой следующей перестановке. Для того чтобы изменение было минимальным, любая перестановка должна отличаться от предыдущей перестановки транспозицией двух соседних (смежных) элементов, где они меняются местами. Например, следующие перестановки на множестве трех первых цифр римской системы счисления {I,V,X} отличаются транспозицией подчеркнутых элементов:
Пт: (IVX); (IXV); (XIV); (XVI); (VXI); (VIX).
В общем случае такая транспозитивная последовательность перестановок легко выстраивается по следующему рекурсивному правилу. Пусть имеется последовательность (n−1)! перестановок из (n−1) элементов, в которой соседние перестановки отличаются транспозицией только двух смежных элементов. Состав каждой из них можно расширить до перестановки из n элементов, добавляя элемент n последовательно на каждую позицию, справа налево для нечетных и слева направо для четных по номеру перестановок из (n−1) элементов. Порядок порождаемых таким способом перестановок элементов множества натуральных чисел {1,2,3} показан на следующей диаграмме:
Рис. 1.  
Из этой диаграммы должно быть понятно, что сначала добавление справа налево элемента 2 в тривиальную одноэлементную перестановку (1) порождает последовательность перестановок из двух элементов:
ПT2: (12); (21).
Затем в каждую из этих перестановок нужно поочередно добавить элемент 3, соответственно, справа налево и слева направо, с учетом четности их порядковых номеров. Это дает в итоге требуемую последовательность перестановок трех элементов:
ПT3: (123); (132); (312); (321); (231); (213).
Следует, однако, отметить, что рассмотренный рекурсивный алгоритм транспозиции смежных элементов не является практически экономичным, потому что приходится порождать целиком весь список последовательностей перестановок П1, П2, …, Пn, когда требуется получить только Пn. Это становится особенно обременительным при генерации перестановок с большим числом элементов n. В связи с указанным обстоятельством, более привлекательным представляется итерационный вариант алгоритма транспозиции смежных элементов, где нет необходимости получать перестановки с меньшим, чем требуется числом элементов.
Рассматриваемый ниже итерационный процесс алгоритма транспозиции смежных элементов реализует последовательность позиционных смещений, когда один из элементов перестановки меняется местами со своим соседом слева или справа в зависимости от текущего направления смещения данного элемента. В результате такого смещения образуется очередная перестановка, которая отличается от предыдущей перестановки только транспозицией этих двух смежных элементов. Следующий пример иллюстрирует технику транспозиции двух смежных элементов pi и pj при смещении элемента pi вправо или элемента pj влево, где направления их смещения обозначены стрелками:
(p1, …,→pi <−> ←pj, …, pn) −> (p1, …,←pj, →pi, …, pn).
Для систематической организации итерационного процесса транспозиций, на каждом его шаге необходимо установить направления смещения всех элементов и выбрать смещаемый элемент. При этом на начальной итерации предъявляется лексиграфически наименьшая перестановка, где для всех элементов задано смещение влево, кроме элемента 1, который никогда не может быть смещен и сохраняет свою первую позицию неизменной на всех последующих итерациях:
(p1= 1, p2=→2, …, pj=→j, …, pn=→n).
На каждой последующей итерации для смещения следует выбирать максимальный элемент pm , который больше своего соседа слева или справа в принятом для него направлении смещения:
pm= max pj | pj−1 < ←pj и j > 1 или →pj > pj+1 и j < n.
Это правило выбора смещаемого элемента можно сделать более компактным, если исключить проверку индексов граничных элементов перестановки и различие индексов соседей. Для этого нужно, во-первых, расширить перестановку слева и справа фиктивными элементами p0 и pn+1 с постоянным значением (n+1). Это автоматически гарантирует выполнение граничных условий:
n+1 = p0 >←p1 и →pn < pn+1= n+1.
Во-вторых, целесообразно ввести функцию кодирования направлений, значения которой d(pj) равны (−1) или (+1) в зависимости от текущих направлений смещения различных элементов перестановки влево или вправо, соответственно, а для начального элемента 1, который никогда не смещается, ее значение принимается равным 0:
d(←pj) = (−1); d(→pj) = (+1); d(1) = 0.
Функция направлений может быть задана в форме вектора указанных значений для элементов перестановки и позволяет однозначно идентифицировать их соседей в направления смещения по алгебраической сумме индексов следующим образом:
j−1 = j + d(←pj) или j+1 = j + d(→pj).
С учетом этих алгоритмических приемов правило выбора смещаемого элемента можно теперь записать в следующей форме, инвариантной относительно индексов и направлений смещений элементов:
pm= max pj > pi, где i = j + d(pj).
Выбранный по этому правилу элемент pm меняется местами со своим соседом в направлении смещения, образуя очередную перестановку, которая отличается от предыдущей перестановкой этих элементов:
pm<−> pi, где i = m + d(pm).
После транспозиции необходимо также инвертировать направления смещения всех элементов, которые больше элемента, выбранного для смещения:
d(pj) = −d(pj) для всех pj> pm.
Аналогичные итерации следует продолжать до последней перестановки, в которой невозможно смещение для всех элементов, потому что любой элемент меньше своего соседа в направлении смещения влево или вправо и, следовательно, pm=1:
pj< pi, где i = j + d(pj) при любых i,j = 1, …, n.
Последовательность итераций рассмотренного алгоритма иллюстрирует следующий пример перечисления перестановок натуральных чисел 1, 2 и 3 в порядке минимального изменения, где подчеркивание выделяет элементы транспозиции, а стрелки и знаки обозначают направления смещения всех элементов на каждой итерации:
ПT: (1, −←2, −←3); (1, −←3, −←2); ( −←3, 1, −←2); ( +→3, −←2, 1); (−←2, +→3, 1); (−←2, 1, →3+).
Любая эффективная алгоритмическая реализация рассмотренного процесса итераций должна обеспечивать быстрый поиск транспозиций без полного перебора всех элементов перестановки. Эта информация легко может быть получена по обратной перестановке, где значения элементов идентифицируют позиции элементов прямой перестановки. Иными словами, значение каждого элемента обратной перестановки определяет порядковый номер позиции, которую занимает в прямой перестановке элемент, равный его индексу. При этом справедливо также двойственное утверждение: значения элементов прямой перестановки равны порядковым номерам позиций своих индексов в обратной перестановке. В частности, если P и R обозначают, соответственно, прямую и обратную перестановки, то между значениями и порядковыми номерами позиций их элементов имеет место, следующее взаимно однозначное соответствие:
ri = j <−> pj = i.
Следующие 2 примера иллюстрируют это взаимно однозначное соответствие. Пусть в обратной перестановке r4=1. Это значит, что в прямой перестановке 4 стоит в первой позиции, поэтому, p1=4. Наоборот, пусть теперь в прямой перестановке, например, p2=1. Тогда первый элемент в обратной перестановке должен быть равен 2, следовательно, r1=2. В общем случае для n элементов такое взаимно однозначное соответствие между прямой и обратной перестановками предоставляет следующий формальный способ вычисления элементов обратной перестановки R по элементам прямой перестановке P:
P−>R: rPj<− j = 1, 2, …, n.
Аналогично можно определить двойственное преобразование, которое восстанавливает прямую перестановку P из n элементов по элементам обратной перестановки R следующим образом:
R−>P: pri<− i = 1, 2, …, n.
В более наглядной форме эти преобразования можно представить следующей иллюстративной схемой. Сначала нужно поменять местами значение и индекс у каждого элемента перестановки, а затем расположить элементы по возрастанию их новых индексов. Указанную схему обработки иллюстрирует следующий пример взаимно обратных преобразований для перестановки из n=4 элементов, где для наглядности указаны индексы элементов:
P = (41123324) −> (14213342) −> (21423314) = R
P = (41123324) <− (12243341) <− (21423314) = R
В алгоритме транспозиции смежных элементов обратные перестановки R следует вычислять на каждой итерации, фиксируя текущие позиции элементов прямой перестановки P. Имея такую информацию, смещаемый элемент можно быстро найти просмотром обратной перестановки в порядке убывания индексов ее элементов (то есть справа налево) и, соответственно, значений элементов прямой перестановки. Этот просмотр нужно продолжать до выполнения условия транспозиции, которое в индексах обратной перестановки выглядит следующим образом:
t = prt> prt+d(t) | t < i < pri+d(i) и d(i) = −d(i).
Далее, аналогично рассмотренной выше основной схеме алгоритма транспозиции смежных элементов, необходимо выбранный для смещения элемент поменять местами со своим соседом в прямой перестановке. Следует также поменять местами элементы обратной перестановки, которые соответствуют индексам элементов транспозиции в прямой перестановке. Это избавит от необходимости каждый раз вычислять обратную перестановку по прямой перестановке для выполнения следующей итерации. В результате этих преобразований будет получена очередная пара прямой и обратной перестановок, которые отличаются от предыдущей итерации только транспозициями следующих элементов прямой и обратной перестановок, соответственно:
prt<−> prt+d(t) ; rPrt<−> rt .
Последовательность итераций рассмотренного алгоритма иллюстрирует следующий пример перечисления прямых и обратных перестановок натуральных чисел 1, 2 и 3, где подчеркивание обозначает элементы транспозиции, а стрелки показывают направления смещения элементов:
По сравнению со всеми другими алгоритмами генерации перестановок итерационный алгоритм транспозиции смежных элементов является самым эффективным, а перечисление перестановок в порядке минимального изменения, которое он обеспечивает, может быть полезно для целого ряда комбинаторных задач. Пусть, например, нужно найти минимум скалярного произведения двух векторов X и Y из n чисел на множестве всех перестановок P элементов вектора X при фиксированном векторе Y:
( P(X), Y=const ) −> min.P
Для решения этой задачи необходимо найти все n! таких скалярных произведений, чтобы иметь возможность выбрать минимальное из них. Эти вычисления будут наиболее эффективны, если перечислять перестановки P(X) в порядке минимального изменения.