Глава 17. Перестановки

Постановка задачи
Идеи реализации
Представление перестановок в программе
Рекурсивная реализация
Итеративные реализации
Разработка
Рекурсивная реализация
Итеративные реализации
Готовая программа
Рекурсивная реализация
Итеративные реализации

Перестановкой множества X, состоящего из n элементов, называется способ упорядочения элементов множества. Поскольку природа элементов множества X не важна, можно считать, что это множество чисел 1 2 3 n .

При каждом способе упорядочения элементов множества X этим элементам ставится в соответствие его порядковый номер — число всё из того же множества X. Это соответствие должно быть взаимно-однозначным (то есть каждому элементу соответствует единственный номер, и наоборот, каждый номер соответствует единственному элементу). Взаимно-однозначные соответствия по-научному называются биекциями.

Как известно, количество перестановок множества равно факториалу количества его элементов.

Множество перестановок n-элементного множества обозначим S n .

Требуется запрограммировать поиск всех перестановок для n, заданного в командной строке. Программу назовём permutations.pl:

(при последнем вызове программы пропущено более 5000 строчек вывода).

Информатика-54© А. Н. Швец