Перестановка из n элементов - это соединения из n различных элементов, взятых в определенном порядке.

Перестановка обозначается буквой P

Формула перестановки из n элементов

P=n!

Итак, допустим нам надо посчитать кол-во перестановок из 3 элементов (допустим n=3). Значит сначала введем эти элементы. Пусть это будут a b c.

Выполним перестановки на бумаге.

a b c (1 перестановка )

a c b (2 перестановка )

b a c (3 перестановка )

b c a (4 перестановка )

c a b (5 перестановка )

c b a (6 перестановка )

Словесный алгоритм будет выглядеть так:
Пока p (нулевое)=0 повторять:

1. Выводим перестановку b[p[i]] .

2. Ищем элемент слева меньший в паре начинаем с конца (это p[j-1]>p[j]) .

3. С конца ищем больший элемент, чем p[j-1]. (это будет p[k] элемент).

4. Меняем местами p[j-1] и p[k].

5. Элементы от p[j] до p[n] меняем в обратном порядке.

Программный алгоритм выглядит так :

Код:
var b:string; p:array [0..255] of integer; c,n,i,j,r,q,d,k:longint;
  begin
   readln(b); 
    n:=length(b);
    
    for i:=0 to n do p[i]:=i;
    
    while p[0]=0 do
     Begin

       for i:=1 to n do write(b[p[i]]);
         writeln;
       
       j:=n;
        while p[j-1]>p[j] do j:=j-1;
       
       k:=n;
        while p[j-1]>p[k] do k:=k-1;
       
       d:=p[k];
       p[k]:=p[j-1];
       p[j-1]:=d;
       
       for i:=j to (n+j-1)div 2 do 
        begin
        d:=p[i];
        p[i]:=p[n-i+j];
        p[n-i+j]:=d;
        end;
    end;
 end.

Отредактировано XApacerX (2011-04-19 16:03:10)