Перейти к содержимому


- - - - -

Перестановка


В этой теме нет ответов

#1 Санек

    Продвинутый пользователь

  • Администраторы
  • 41 сообщений
  • ГородВитебск

Отправлено 22 декабря 2011 - 12:35

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






Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных