Учебно-методическое пособие. Алматы, 2017 ббк

abc, acb, bac, bca, cab, cba.

Количество всех способов, которыми можно переставить N различных предметов, расположенных на N различных местах, принято обозначать Р^N(читается: <число перестановок из N>).

Найдем Р^N. На первое из имеющихся мест предмет может быть выбран N способами, на второе место - (N - 1) способом, на третье место - (N - 2) способами и т. д. На предпоследнее место предмет выбирается из двух остав­шихся, а для последнего места выбор предмета единственен. Общее количество способов будет равно произведению N (N- 1)* (N - 2) ... * 2 * 1. Такое произведение называется факториалом числа N и обозначается N!.

Таким образом, Р^N = N!.
Иногда требуется не просто подсчитать количество перестановок из n элементов, но и найти каждую из них. Существует несколько алгоритмов генерации всех перестановок из n элементов. Они различаются порядком генерации перестановок.

Рассмотрим один из хорошо известных алгоритмов, в процессе исполнения которого перестановки располагаются лексикографически (в словарном порядке). Это значит, что перестановки сравниваются слева-направо поэлементно и большей из них является та, у которой раньше встретился элемент, больший соответствующего ему элемента во второй перестановке. (Например, если S=(3, 5, 4, 6, 7), а L=(3, 5, 6, 4, 7), то S < L.)

Приведем фрагмент программы, генерирующей все перестановки в лексикографическом порядке:

for i:= 0 to n do

p(i) :=i;

while p(0)=0 do

begin

for i:= 0 to n do

j=N

j =j+1

k=N

k=k - 1

d=p(j-1)

p(j-1)=p(k)

p(k)=d

r(i) =p(N-i+j)

next i

for i = j do n

p(i) =r(i)

next i