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

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

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

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

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

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

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

p_i < p_i+1 | p_k > p_k+1 при любых k > i.

В данном случае (p_i=5)<(p_i+1=8). Затем следует найти наименьший элемент p_j справа от p_i, который больше p_i:

В данном случае p_j=7. Далее нужно поменять местами p_i=5 с p_j=7 и перестановка выглядит уже так:

Наконец, хвост перестановки, начиная с p_i+1=8, необходимо записать в обратном порядке, и в итоге получается лексиграфически следующая перестановка:

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

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

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

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

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

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

B_i+1 = [(p₁, … p_j=i, … p_n=i+1)]_i+1 (pj = i <−> pn = i+1) > B_i = [(p₁, … p_j=i+1, … p_n=i)]_i.

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