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

M - по сколько символов в сочетании

Основная идея генерации таких сочетаний с повторениями заключается в следующем:

Сочетания записываем в виде (N-1)-го нуля и M единиц ,где единицы заменяют символы, а нули выступают в pоли pазделителей.

Напpимеp:

ABB - 1 0 1 1 AAC - 1 1 0 0 1 C C C - 0 0 1 1 1

A B B A A C C C C

При таком подходе для решения задачи достаточно сгенерировать все перестановки из M единиц и N-1-го нуля.

Ниже приводится программа, которая решает поставленную задачу.

const

alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

b : array [1..100] of byte;

N,i,j,k,M,N1 : byte;

Procedure SwapB(i,k:byte);

var x : byte;

begin

x:=B[i]; B[i]:=B[k]; B[k]:=x;

end;

Procedure WriteB;

var i,j : byte;

begin

j:=1;

for i:=1 to N do

if b[i]=0

then Inc(j)

else write(alphabet[j]);

writeln;

end;

begin