На множестве P всех перестановок <x₀, x₁, ..., x_n-1> из элементов {1, 2, …, n} определим два типа порядка.

Лексикографический порядок на P вводится так [42, c.25; 26]. Пусть

<a₀, a₁, ..., a_n-1>, <b₀, b₁, ..., b_n-1>ÎP                                            (3)

и символ <’ (меньше) используется в качестве знака лексикографического сравнения перестановок. Тогда считаем, что:

<a₀, a₁, ..., a_n-1>, <' <b₀, b₁, ..., b_n-1> Û   $ (0 £ k £ n-1) [(a_k < b_k) Ù"(s < k)(a_s = b_s)].  (4)

Заметим, что если вместо чисел 1,2,…,n использовать буквы с естественным порядком следования их в алфавите, то лексикографический порядок определяет стандартную последовательность, в которой слова длины n появляются в словаре. И это справедливо для алфавитов любых языков.

Аналогично вводится и антилексикографический порядок [42, c.25] на P. Пусть символ <” (меньше) используется в качестве знака антилексикографического сравнения перестановок. Тогда для (3) считаем, что:

<a₀, a₁, ..., a_n-1>, <' <b₀, b₁, ..., b_n-1> Û   $ (0 £ k £ n-1) [(a_k > b_k) Ù"(s > k)(a_s = b_s)].  (5)

адача 3. Написать рекурсивную программу-функцию генерирования всех перестановок из n элементов 1,2,…,n в антилексикографическом порядке.

Решение. Соответствующий алгоритм может базироваться на следующих двух утверждениях, непосредственно вытекающих из определений (3)-(4).

Утверждение 1. Если множество перестановок P упорядочено антилексикографически, то начальная и конечная перестановки - это соответственно <1, 2, …, n> и < n, n-1,…,1>.

Утверждение 2. Упорядоченная антилексикографически последовательность перестановок по значению последнего элемента в них может быть разбита на n блоков длины (n-1)!. При этом q-й блок на последнем месте имеет элемент, равный (n-q+1), а первые n-1 позиций этого блока определяют последовательность перестановок множества {1,2,…,n}\{q} в антилексикографическом порядке.

Головная функция permut3(n) решает поставленную задачу. В ней по значению n для рекурсивной программы-функции permu(p) формируется начальная перестановка p. В permu(p) и проводятся все вычисления. На рисунке 3 представлен результат выполнения permut3(n) при n=3 и n=4. Для n=4 полученные последовательные перестановки расположены по строкам сверху вниз и столбцам от первого и до последнего.

                              (6)

                                                    (7)

Рис. 3. Генерирование перестановок в антилексикографическом порядке