0
Размещение обозначается буквой A
Формула размещения
А= n! / ( n-m )!
Теперь устная задача
Задача
Найти сколько вариантов из 3-х букв a b c можно составить 2-х буквенных слов.
Попробуем на бумаге:
(1 перестановка ) a b (3 перестановка ) a c (5 перестановка ) b c
(2 перестановка ) b c (4 перестановка ) c a (6 перестановка ) c b
Получается 6 вариантов.
Теперь проверим нашу формулу
А=3!/(3-2)1=6/1=6
Значит формула правильная.
Ответ: 6 вариантов.
Алгоритм
Тут нам понадобится совместить алгоритм сочетания и алгоритм перестановки .
В алгоритме сочетания ( смотри ниже).
1. Пересохраняем массив p в q.
2. Делаем перестановку из m элементов на ходящихся в массиве q.
3.Теперь меняем элементы с помощью сочетания.
//----------------------------------------------------------------------------------//
// Название: GeneralDeployment //
// Автор кода(именно кода): Andrew (Krasnobaev) //
// Сайт: redcode.do.am (временно пуст) //
// Описание: Размещение, занесённое в запись, в качестве метода(классов то тут нет) //
//----------------------------------------------------------------------------------//
type
ArrType = array[0..65536] of byte;
DepType = array[0..10000] of ArrType;
Comb_Class = record
procedure IntGeneralDeployment(ArrLength, DepLength: longint; Arr: ArrType; var DepArr: DepType; var DepCount: LongInt);
var
p, q: array [0..10000] of byte;
i, j, k, d: longint;
begin
DepCount := 0;
for i := 1 to ArrLength do p[i] := i;
repeat
for i := 0 to DepLength do q[i] := p[i];
while q[0] = 0 do
begin
while q[0] = 0 do
begin
inc(DepCount);
for i := 1 to DepLength do DepArr[DepCount][i] := Arr[q[i]];
j := DepLength;
while q[j - 1] > q[j] do dec(j);
k := DepLength;
while q[j - 1] > q[k] do dec(k);
d := q[j - 1];
q[j - 1] := q[k];
q[k] := d;
for i := j to (DepLength + j - 1) div 2 do
begin
d := q[DepLength + j - i];
q[DepLength + j - i] := q[i];
q[i] := d;
end;
end;
end;
j := DepLength;
while (j > 0) and (p[j] = j + ArrLength - DepLength) do dec(j);
if j > 0 then begin
p[j] := p[j] + 1;
for i := j + 1 to DepLength do p[i] := p[i - 1] + 1;
end;
until j = 0;
end;
end;
var
Combinatorics: Comb_Class;
ArrLength: 0..65536;
DepLength, DepCount, i, j: LongInt;
Arr: ArrType;
DepArr: DepType;
begin
//Ввод и настройка параметров
writeln('Entering:');
read( ArrLength, DepLength );
for i:=1 to ArrLength do read(Arr[i]);
//Само размещение
Combinatorics.IntGeneralDeployment( ArrLength, DepLength, Arr, DepArr, DepCount );
//Вывод
writeln;
writeln('Result:');
for i:=1 to DepCount do begin
write('Deployment №',i,' is ( ');
for j:=1 to DepLength do write(DepArr[i][j],' ');
writeln(' );');
end;
writeln('There are ',DepCount,' Deployments');
writeln('Press <Enter> to finish :');
readln;
end.
