Перестановкой множества $X$ , состоящего из $n$ элементов, называется способ упорядочения элементов множества. Поскольку природа элементов множества $X$ не важна, можно считать, что это множество чисел $\{123 \dots n\}$ .

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

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

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

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

% ./permutations.pl 2
1 2
2 1
% ./permutations.pl 3
3 2 1
2 3 1
2 1 3
3 1 2
1 3 2
1 2 3
% ./permutations.pl 7
7 6 5 4 3 2 1
6 7 5 4 3 2 1
6 5 7 4 3 2 1
6 5 4 7 3 2 1
6 5 4 3 7 2 1
6 5 4 3 2 7 1
6 5 4 3 2 1 7
7 5 6 4 3 2 1
5 7 6 4 3 2 1
5 6 7 4 3 2 1
5 6 4 7 3 2 1
…
1 7 2 3 4 5 6
1 2 7 3 4 5 6
1 2 3 7 4 5 6
1 2 3 4 7 5 6
1 2 3 4 5 7 6
1 2 3 4 5 6 7

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

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

Постановка задачи


Готовая программа		Идеи реализации