Наиболее естественно выглядит результат перечисления перестановок в лексиграфическом порядке, где каждая следующая перестановка образует лексиграфически больший вектор своих элементов, чем любая из предыдущих. В общем случае из 2-х векторов с равным числом элементов лексиграфически больше тот, у которого больше первый из несовпадающих элементов. Применительно, например, к цифровым перестановкам лексиграфический порядок порождает возрастающую последовательность натуральных чисел, которые получаются из записей соответствующих перестановок. В частности, перестановки из 3-х цифр 1, 2 и3 образуют следующую лексиграфически упорядоченную (числовую) последовательность:

П: (1 2 3)< (1 3 2)< (2 1 3)< (2 3 1)< (3 1 2)< (3 2 1)

Лексиграфический порядок перестановок букв различных национальных алфавитов соответствует расположению образованных слов как в словаре. Например, перестановки 3-х последних латинских букв X, Y, и Z могут быть перечислены в следующем лексиграфическом (словарном) порядке:

П: (X Y Z)< (Y X Z)< (Y Z X)< (Z X Y) < (Z Y X).

Однако, без потери общности описания лексиграфического алгоритма удобно рассматривать перестановки целых чисел от 1 до n. Этот алгоритм реализует итерационный процесс, который начинается с лексиграфически наименьшей перестановки, где все числа расположены в порядке возрастания их величин: (1, 2, … n). Например, лексиграфически наименьшая числовая перестановка из 8-и элементов имеет вид:

Р= (1, 2, 3, 4, 5, 6, 7, 8).

На каждой следующей итерации рассматривается текущая перестановка целых чисел: (p₁, ...p_i, ... p_j, ... P_n). Пусть, например, на предыдущей итерации была получена такая перестановка:

Р= (2, 6 , 5, 8, 7, 4, 3, 1).

Для преобразования ее в очередную перестановку в лексиграфическом порядке нужно выполнить следующие действия:

1. Путем просмотра текущей перестановки справа налево найти самый правый элемент ???, который меньше своего соседа справа p_i+1:

p_i<p_i+1|p_k>p_k+1 при любых k>i; в данном примере p_i=5 < P_i+1=8??????????

2. Найти наименьший элемент P_j справа от P_i, который больше P_i:

P_j=P_k|P_k>p_i; в данной ситуации P_j=7=min(8,7>p_i=5)

3. Поменять местами P_i=5 и p_j=7 перестановка выглядит теперь так:

p=(p₁,...p_j,Pi+1,... p_i, p_j+1, ... P_n)= (2,6,7,8,5,4,3,1)

4. Хвост перестановки, начиная с ??? записывается в обратном порядке и окончательно получается лексиграфически следующая перестановка:

p=(p₁,...p_j,pn,... p_j+1, p_i, ... P_i+1)= (2,6,7,1,3,4,5,8)

Аналогичный итерации нужно продолжать до получения лексиграфически наибольшей перестановки, где все числа расположены в порядке убывания их величин:

Р= (n, … 2, 1)= (8, 7, 6, 5, 4, 3, 2, 1).

Рассмотренный лексиграфический алгоритм несложно приспособить для порождения перестановок в обратном лексиграфическом порядке. В этом порядке последовательность перестановок начинается с лексиграфически наибольшей, а каждая следующая перестановка лексиграфически меньше предыдущей. Чтобы получить такой порядок лексиграфическим алгоритмом нужно заменить на противоположные все знаки отоношения сравнения жлементов и поиск наименьшего элемента заменить поиском наибольшего.

Следует отметить, что в обоих вариантах лексиграфического порядка сравнение перестановок производилось по первому несовпадающему элементу. Если для сравнения перестановок использовать последний несовпадающий элемент, то образуется противоположный порядок перечисления перестановок, который принято называть антилексическим. Формально, последовательность перестановок считается перечисленной в антилексиграфическом порядке, когда для любой пары последовательных перестановок P' и P'' справедливо следующее соотношение элементов: существует такой индекс j, что P_j'>P_j'' и P_i'= P_i'' при всех i>j. Например, отношение антилексического порядка выполняется для следующей пары цифровых перестановок, P' и P'', где символ ‘^’ обозначает их последние несовпадающие элементы:

P'=(1,3,2,4) <(3,1,2,4)=P''

- ^~~ ^~~

По определению антилексиграфическую последовательность перестановок можно получить, если изменить на противоположное расположение элементов во всех перестановках, которые перечислены в обратном лексиграфическом порядке. Однако, существует специальный рекурсивный алгоритм, который непосредственно формирует антилексиграфическую последовательность перестановок.

В этом алгоритме последовательность n-перестановок формируется из блоков уже полученных (n-1)-перестановок, в которые по определенным правилам добавляется элемент n. Каждый блок состоит из (n-1)! Перестановок и всего формируется n блоков, которые нумеруются целыми числами от n до 1:

П_A: <B_n, ... B_i, ... B₁>

Начальный блок B_n образует все уже построенные рекурсивно (n-1)-перестановки, в каждую из которых справа добавлен элемент со значением n:

B_n=[(P₁, ... P_j, ... P_n-1, P_n=n)]_n

Каждый следующий блок с номером i=n-1, n-2, … 1 должен состоять из (n-1)! перестановок, где последний элемент имеет значение i. При этом перестановки блока B_i получаются транспозицией элементов со значениями i и (i+1) в перестановка предыдущего блока B_i+1, во всех перестановках которого последний элемент имеет значение (i+1). Это преобразование блока B_i+1 в блок B_i можно условно записать следующим образом:

- P_j=i<->P_n=i+1

B_i+1=[(P_i,...P_j=i,... P_n=i+1)]_i+1=========>B_i=[(P₁, ....P_j=i+1, ... P_n=i)]_i

Указанный процесс преобразований завершается форматированием блока B₁, где значение последнего элемента всех перестановок равно единице. Таким образом получается антилексиграфическая последовательность n(n-1)! перестановок из n элементов, которая может быть рекурсивно использована для построения перестановок высших порядков. Рассмотренный алгоритм иллюстрирует следующий пример формирования цифровых перестановок их 3-х элементов, где каждый блок выделен парой квадратных скобок [], а символы '^' обозначают добавление и транспозиции элементов:

- +3 3<->2 2<->1

[(12);(21)==>[(123);(213)]₃==>[(132);(312)]₂==>[(231);(321)]₁

- ^ ^ ^^ ^ ^ ^ ^ ^^