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

Решение. В предыдущем разделе мы ввели понятие лексикографического порядка. Алгоритм генерирования перестановок в таком порядке и соответствующие программы-функции могут быть построены на идеях, близких к тем, которые использовались при генерировании перестановок в антилексикографическом порядке. Поэтому здесь мы ограничимся лишь приведением соответствующих функций permut(p) и permut4(n) и представим полученный по ним результат вычислений для n=3 и n=4 (рис.4). Для n=4 полученные перестановки расположены по строкам сверху вниз и столбцам от первого и до последнего.

                               (8)

                                                   (9)

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