олимпиадники-информатики

Перестановка из 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.

Те, кто не любит писать много кода, знайте, перестановки можно написать рекурсивно. Вот сам код:

 
var a: array[0..1001] of longint;
    index,n: longint;
procedure generate(l,r:longint);
var i, v: integer;
begin
  if (l = r) 
    then
      begin
        for i := 1 to n do
        write(a[i], ' ');
        writeln;
      end
      else
        begin
          for i := l to r do
            begin
              v := a[l];
              a[l] := a[i];
              a[i] := v; {обмен a[i],a[j]}
              generate(l + 1, r); {вызов новой генерации}
              v := a[l];
              a[l] := a[i];
              a[i] := v; {обмен a[i],a[j]}
            end;
        end;
end;
begin
  readln(n);
  for index := 1 to n do
    A[index] := index;
  generate(1, n);
end.

Сообщение отредактировал Санек: 15 ноября 2012 - 14:39