Реферат: Комбинаторные задачи

По формулам (7) можно подсчитать, что в рамках принятых выше допущений можно построить все разбиения множества, состоящего не более чем из 15 элементов (B ₁₅ =1382958545).

Перейдем теперь к рассмотрению способа генерации всех разбиений исходного множества. Прежде всего, следует договориться о том, как обозначать текущее разбиение. Так как в каждом из разбиений участвуют все элементы исходного множества, будем в массиве индексов p записывать в какой блок попадает каждый из элементов в текущем разбиении. Параметр i в рекурсивной процедуре partозначает, что на текущем шаге мы именно i-ый элемент будет размещать в каждом из допустимых для него блоков, а j как раз и определяет максимальный номер допустимого блока. После того, как i-ый элемент помещен в один из блоков, рекурсивно решается такая же задача уже для следующего элемента (в данном случае фактически работает универсальная схема перебора с возвратом [8]).

procedure partition(n : integer; var p:list);

procedure part(i, j: integer);

var l: integer;

begin

if i > n then print(n, p) else

for l := 1 to j do

begin

p[i] := l;

if l = j then part(i+1, j+1)

else part(i+1, j)

end

end; {part}

begin { partition }

part (1,1)

end ;

Как ни странно, в данном случае процедура print оказывается совсем не тривиальной, если требуется печатать (или анализировать) элементы каждого из блоков разбиения в отдельности. Поэтому приведем возможный вариант ее реализации (как и ранее, распределяли по блокам мы индексы, а печатаем или анализуруем сами элементы исходного массива a):

procedure print(n:integer; var p:list);

var i,j,imax:integer;

begin

imax:=1;{определяем количество блоков в разбиении}

for i:=2 to n do

if p[i]>imax then imax:=p[i];

for i:=1 to imax do { цикл по блокам }

begin

for j:=1 to n do

if p[j]=i then write(a[j]:4);