При S={1} имеем одну перестановку - 1. Если уже имеется последовательность перестановок из n-1 элемента {1,2,…,n-1}, то получить все перестановки из n элементов {1,2,…n} можно способом, который мы будем именовать как “метод вертикальной прогонки” элемента n. Суть его в следующем. Рассмотрим n идентичных экземпляров (групп) последовательностей перестановок из элементов {1,2,…,n-1}. В первом экземпляре в конец каждой перестановки поместим элемент n. Во втором экземпляре этот элемент поместим на предпоследнем месте и т.д. Наконец, в последнем экземпляре поместим n перед первым элементом. На рис.1 описанная процедура демонстрируется при переходе от n=3 к n=4. Нетрудно понять, что указанные действия любую перестановку из n-1 элемента переводят в некоторую перестановку из n элементов. При этом общее количество полученных перестановок равно n!. Остается показать, что среди них нет совпадающих. Если взять две сгенерированные перестановки внутри одной группы, то они будут различаться позициями элементов {1,2,…,n-1} и, значит, не могут быть совпадающими. Если же взять перестановки из разных групп, то позиции элемента n в них будут разными и перестановки опять не могут быть совпадающими. Таким образом, все полученные n! перестановок различны.

Рис. 1. Генерирование перестановок вертикальной прогонкой

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

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

                             (1)

Контрольный пример: