Перестановка
Санек
21 дек 2011
Перестановка из 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.
MakTraDe
23 дек 2011
Те, кто не любит писать много кода, знайте, перестановки можно написать рекурсивно. Вот сам код:
Сообщение отредактировал Санек: 15 ноября 2012 - 14:39
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