Реферат: Генерация комбинаторных объектов

for i:=1 to M do write(alphabet[b[i]]);

writeln;

end;

begin

readln(N,M);

for i:=1 to M do b[i]:=i;

WriteB;

while (true) do

begin

i:=M;

while (i>0) and (b[i]=N-m+i) do Dec(i);

if i=0 then exit;

Inc(B[i]);

for j:=i+1 to M do B[j]:=B[j-1]+1;

WriteB;

end;

end.

Напомним, что общее число сочетаний из N элементов по M может быть вычислено по формуле C (N,M) = N! / (M! * (N-M)! )

4 Размещения

Для генерации всех размещений из N элементов по M можно воспользоваться композицией алгоритмов, изложенных выше. То есть генерировать все сочетания из N по M, а затем для каждого полученного сочетания генерировать все перестановки из M элементов.

Например, при генерации всех размещений из 5 элементов по 3, в случае, если сами элементы обозначены латинскими буквами A,B,C,D,E нужно получить следующую последовательность, представленную для компактности в виде 10 строк, каждая из которых представляет все возможные сочетания из 3 букв первого элемента строки. А сами первые элементы строк как раз и представляют все возможные сочетания из 5 букв по 3.

ABC ACB BAC BCA CAB CBA

ABD ...

ABE ...

ACD ...

ACE ...

ADE ...

BCD ...

BCE ...