Введение
В наш бурно развивающийся век, казалось бы, всеалгоритмы, которые можно придумать, уже придуманы. Но иногда встречаютсязадачи, для которых нет подходящих алгоритмов. Быть может потому, что задачаредко встречается или, скорее всего для этой задачи нет эффективных алгоритмов(а, скорее всего, их и вовсе не существует).
В этой работе будет обсуждаться темаразбиений множеств.
В [1] автор даёт несколько таких алгоритмов:генерирование всех подмножеств n-элементного множества, генерирование всех k-элементныхподмножеств множества {1, …, n} в лексикографическом порядке, генерирование всехразбиений множества {1, …, n} (на этом алгоритме остановимся подробней),нахождение всех разбиений числа.
Первый из этих алгоритмов использует идею бинарногокода Грэя, остальные основаны на удалении или добавлении одного элемента.Последний алгоритм использует схему разбиения большего числа на меньшие числа.
Постановка задачи
Формулировка первой задачи, которую мырассмотрим, выглядит так: необходимо сгенерировать все разбиения множества,содержащего n элементов.
Для формулировки второй задачи необходимоввести некоторые понятия.
Итак, дано множество, состоящее из nэлементов. Каждый элемент этого множества образует некоторое понятие. Два илибольше понятия могут быть объединены в новое понятие. Отличительная чертапонятий – взятие их в круглые скобки.
Задача выглядит так: сгенерировать всепонятия, которые могут быть образованы из n элементов.Например, для n=3 имеем такие понятия (круглые скобки в начале и вконце опущены для краткости): (*)**, (*)(*)*, (*)(*)(*), (**)*, (**)(*),((*)*)*, ((*)*)(*), ((*)(*))*, ((*)(*))(*).
Математическое обоснование
Под разбиением n-элементногомножества Х на k блоков будем понимать произвольное семейство />, такое, что /> для 1£і для1£i£k. Подмножества /> будемназывать блоками семейства π. Множество всех разбиений множества Х на kблоков будем обозначать />, амножество всех разбиений через П(Х). Очевидно, что /> (болеетого, /> является разбиением множестваП(Х)).
Число Стирлинга второгорода S(n,k) определяетсякак число разбиений n-элементного множества на k блоков:
/> где |X|=n.
Очевидно, что S(n,k)=0для k>n. Принимают также S(0,0)=1, таккак пустое семейство блоков является в соответствии с определением разбиениемпустого множества. С числами Стирлинга второго порядка связано много любопытныхтождеств:
S(n,k)=S(n-1,k-1)+kS(n-1,k) для 0
S(n,n)=1 для n≥0, (2)
S(n,0)=0 для n>0.(3)
Формулы (2) и (3) очевидны.Для доказательства формулы (1) рассмотрим множество всех разбиений множества{1, …, n} на k блоков. Это множество распадается на два различныхкласса: тех разбиений, которые содержат одноэлементный блок {n}, итех разбиений, для которых n является элементом большего (по крайней мере,двухэлементного) блока. Мощность первого класса равна S(n-1,k-1),т. е. такова, каково число разбиений множества {1, …, n-1} на (k-1)блоков. Мощность другого класса составляет kS(n-1,k),так как каждому разбиению множества {1, …, n-1} на kблоков соответствует в этом классе в точности k разбиений,образованных добавлением элемента n поочерёдно к каждому блоку.
Формулы (1)-(3) позволяютлегко вычислять значения S(n,k) даже длябольших значений n и k.
Вот другая рекуррентнаязависимость:
/> для k≥2. (4)
Для доказательства тождестварассмотрим множество всех разбиений S(n,k)множества Х={1, …, n}. Это множество распадается на различные классы,соответствующие разным подмножествам множества Х, которые являются блоками,содержащими элемент n. Отметим, что для каждого b-элементногоподмножества /> содержащего элемент n,существует в точности S(n-b,k-1) разбиений множества Х на k блоков,содержащих В в качестве блока. Действительно, каждое такое разбиение однозначносоответствует разбиению множества Х\В на k-1 блоков. b-элементноемножество /> содержащее элемент n,можно выбрать /> способами; такимобразом,
/>
Число Белла /> определяется как число всех разбиений n-элементногомножества
/> где |X|=n.
Другими словами,
/>
Докажем рекуррентную зависимость, связанную счислами Белла:
/> (5)
(принимаем />).Доказательство проводится аналогично доказательства тождества (4). Множествовсех разбиений множества Х={1, …, n+1} можно разбить на различныеклассы в зависимости от блока В, содержащего элемент n+1, или – чторавнозначно – в зависимости от множества Х\В. Для каждого множества /> существует в точности /> разбиений множества Х,содержащих В в качестве блока. Группируя наши классы в зависимости от мощностимножества Х\В, получаем формулу (5).
Теперь опишем алгоритм генерирования всехразбиений множества.
Отметим, что каждое разбиение p множества {1,…, n} однозначно определяет разбиение /> множества {1,…,n-1},возникшее из p после удаления элемента n изсоответствующего блока (и удалению образовавшегося простого блока, если элементn образовывал одноэлементный блок). Напротив, если даноразбиение /> множества {1, …, n-1},легко найти все разбиения π множества {1, …, n}, такие что />, т. е. следующиеразбиения:
/>
Если нам дан список /> всехразбиений множества {1, …, n-1}, то список /> всехразбиений множества {1, …,n}, будем создавать, заменяя каждое разбиение σ всписке /> на соответствующую емупоследовательность (6). Если обратить порядок последовательности (6) длякаждого второго разбиения />, тоэлемент n будет двигаться попеременно вперёд и назад, иразбиения «на стыке» последовательностей, образованных из соседних разбиенийсписка /> мало отличаются один отдругого.
Разбиение множества {1, …, n} мыбудем представлять с помощью последовательности блоков, упорядоченной повозрастанию самого маленького элемента в блоке. Этот наименьший элемент блокамы будем называть номером блока. Отметим, что номера соседних блоков, вообщеговоря, не являются соседними натуральными числами. В этом алгоритме мы будемиспользовать переменные pred[і], sled[і], 1≤і≤n, содержащиесоответственно номер предыдущего и номер следующего блока с номером і (sled[і]=0, если блокс номером і является последнимблоком разбиения). Для каждого элемента і, 1≤і≤n,номер блока, содержащего элемент і,будет храниться в переменной blok[і],направление, в котором «движется» элемент і, будетзакодировано в булевской переменной wper[і] (wper[і]=true,если і движется вперёд).
Можно показать, что среднее число шагов,необходимых для построения каждого следующего разбиения, ограничено постоянной,не зависящей от n(конечно, если не учитывать число шагов, необходимыхдля написания разбиения).
( 1 2 3 4 )
( 1 2 3 )( 4 )
( 1 2 )( 3 )( 4 )
( 1 2 )( 3 4 )
( 1 2 4 )( 3 )
( 1 4 )( 2 )( 3 )
( 1 )( 2 4 )( 3 )
( 1 )( 2 )( 3 4 )
( 1 )( 2 )( 3 )( 4 )
( 1 )( 2 3 )( 4 )
( 1 )( 2 3 4 )
( 1 4 )( 2 3 )
( 1 3 4)( 2 )
( 1 3 )( 2 4 )
( 1 3)( 2 )( 4 )
Табл.1.Последовательность разбиений множества {1,2,3,4}
Опишем теперьалгоритм решения задачи о перечислении всех понятий.
Рекурсивный алгоритм использовать нельзя, таккак все решения подзадачи меньшей размерности необходимо скомбинировать совсеми решениями подзадачи оставшейся размерности. Поэтому, будем простоперебирать все варианты.
Идея такова: сохраняем все разбиения меньшейразмерности и комбинируем их так, чтобы
1) они не повторялись;
2) количество элементов нового разбиения не было быбольше количества элементов n.
Итак, пусть мы имеем дваначальных состояния: (*) и *. Для n=2 имеем только одно выходноепонятие: (*)*. Для n=3 необходимо скомбинировать все известные ранеесостояния с учётом условий 1)-2).
Условие 1) обеспечим изтаких соображений: каждому элементу присвоить порядковый номер и комбинироватьпонятия так, чтобы порядковый номер следующего понятия не превосходилпорядковый номер предыдущего понятия, а также следить, чтобы выполнялосьусловие 2). Отсюда видно, что повторений не будет, и мы перечислим все понятия.
Для реализации условия 2) необходимо каждомупонятию присвоить число, которое будет показывать количество элементов этогосостояния.
Также необходимо иметь некоторый массив,каждый элемент которого будет указывать на понятие, соответствующее номерупонятия в выходном понятии. Элементы этого массива будут меняться, всоответствии с перебором вариантов.
Язык программирования
Для реализации алгоритмов был выбран языкпрограммирования Turbo Pascal 7.0. В этом языке есть всенеобходимые средства для этих алгоритмов, и сам язык является простым дляпонимания. Поэтому выбор пал именно на него.
Для алгоритмов нам понадобятся понятияуказателей и записей.
Запись в Pascal’е описываетсятак:
=|:record
end;
Например,
Var point:record
x,y: integer;
color:byte
end;
Обращаются к полям записи так:
Nx:=point.x+point.y;
Point.color:=3;
Указателиописываются так:
=|:^имя типа>
Например,k:^integer–указатель на целое. Обращение к содержимому указателя: t:=k^, а запись значения в ячейку памяти, куда указывает k,выглядит так: k^:=10. Но, чтобі использовать указатели, необходимо сначала выделить память под них. Это делается с помощьюкоманды new:
New(k);
Чтобы освободить память, если указатель ужене будет нужен, используют
Dispose(k);
Операторыприсваивания, арифметических операций и циклов похожи во многих языках, поэтомуих описывать не стоит.Реализация алгоритмовГенерирование разбиений множества
В табл.1 представлены разбиения для n=4,генерируемые следующим алгоритмом:
program razbienie_mnozhestwa(input,output);
var i,j,k,n:byte;wper:array[1..255]ofboolean;
sled,pred,blok:array[1..255]of byte;
procedure write_razbienie; {процедура, выписывающаяразбиение на экран}
var
i,j:byte;
begin
j:=1; {номер первого блока}
repeat
write(‘( ‘);
for i:=j to n do if blok[i]=j thenwrite(i, ‘ ‘); {есличислоіизблокаj, топишемэточисло}
j:=sled[j]; {следующий по номеру блок}
write(‘)’);
until j=0;
WRITELN
end;
begin
write(‘input n:’);
readln(n);{вводим количество элементов множества}
fori:=1 to n do begin {строимразбиение{{1, …, n}}}
blok[i]:=1;
wper[i]:=true
end;
sled[1]:=0;
write_razbienie; {выписатьразбиение}
j:=n;{активный элемент}
while j>1 do begin {задача цикла – перемещение«активного» элемента jв соседний блок – в предыдущий или последующий (в последнем случаеможет возникнуть необходимость создания нового блока вида {j}, а затем определение активного элемента во вновь образованномразбиении}
k:=blok[j]; {процесс переноса активного элемента;k– номер активного блока}
if wper[j] then begin {j движетсявперёд}
if sled[k]=0 then begin {k – последнийблок}
sled[k]:=j; {j– одноэлементный блок}
pred[j]:=k;
sled[j]:=0
end;
if sled[k]>j then begin {j образуетновыйблок}
pred[j]:=k; {все блоки справа от блока с номером kсодержатэлементы,большие j. Отсюда следует, что jобразует новый одноэлементныйблок}
sled[j]:=sled[k];
pred[sled[j]]:=j;
sled[k]:=j
end;
blok[j]:=sled[k] {переносим наш элемент в активный блок с номером k}
end
else begin {j движетсяназад}
blok[j]:=pred[k]; {помещаемj впредыдущийблок}
if k=j then if sled[k]=0 thensled[pred[k]]:=0 else begin
sled[pred[k]]:=sled[k];
pred[sled[k]]:=pred[k]
end
end;
write_razbienie;
j:=n;
while(j>1)and
((wper[j]and(blok[j]=j))or(notwper[j]and(blok[j]=1))) do begin
wper[j]:=not wper[j];
dec(j)
end
end
end.
Количествовсех разбиений можно посчитать используя числа Белла и рекуррентную формулу(5).
Генерирование всех понятий
Дляреализации данной задачи на Pascal’е вводим следующие типы данных и переменных:
1) тип k – указатель на запись, поля которой: s –будет содержать понятие; p – количество элементов в понятии; next– ссылка на следующее понятие;
2) переменныеf, pot типа k; f – указывает на первое понятие, то есть на простоепонятие *; pot – текущее понятие;
3) массив str1 типа k – будет содержать ссылки на каждое понятие всоставном понятии;
programdyscretics_optimisation(input,output);
uses crt;
const
max=12;
r:byte=0;
type
k=^el;
El=record
S: string;
P: 1..Max-1;
Next: k
End;
Label met;
Var
Pot, f, l: k;
Str1: array[1..Max]of k;
Pow: 2..Max;
K1, i, j, ll: 1..Max;
Sum: 0..Max;
Fil: text;
Ki: string[2];
begin
Readln(POW); {вводим количество простых понятий}
Str(POW,ki);
Assign(fil, ki+’.mvp’); {получившиеся понятия будем записывать в файл, содержащий в своём имени количество элементов множества и срасширением «.mvp»}
Rewrite(fil);
New(f); {выделяем память под первое понятие}
Pot:=f;
F^. S:=’*’; {и инициализируем его}
F^. P:=1;
New(f^.next); {выделяем памятьпод второе понятие}
Pot:=f^.next;
Pot^.s:='(*)’; {и также его инициализируем}
Pot^.p:=1;
Pot^.next:=nil;
for i:=2 to POW do begin {основнойциклпрограммы}
Forj:=1 toidostr1[j]:=f;{устанавливаем начальные указатели понятия, размерности і, на первое понятие}
Ifi=POWthenstr1[1]:=f^.next; {если і равно количеству элементов множества, то необходимоизменить указатель на первое подпонятие нашего понятия, так как уже отмечалосьвыше, понятие, состоящее только из простых подпонятий выводить не надо. Но,такие понятия оставляем для подзадач меньшей размерности, так как в комбинациис решениями других подзадач, получим уже понятие, содержащее не только простыепонятия}
Whilestr1[1]nildobegin{пока указатель первого подпонятия не достигнетконца списка подпонятий выполнять}
New(pot^.next); {выделить память под очередное понятие}
Sum:=0; {эта переменнаяслужит в качестве счётчика, который после следующего цикла будет содержатьколичество элементов в новом понятии}
K1:=1; {номер первогоподпонятия. Первое подпонятие имеет всегда, если можно так выразиться, «болеепоздний адрес», или, точнее, все подпонятия, следующее за первым, полученыраньше или одновременно с ним. Это также касается второго подпонятиеотносительно третьего, четвёртого и т. д., третьегоотносительно четвёртого, пятого и т. д., и т. д.}
Ifi=powthenpot^.next^.s:=” elsepot^.next^.s:='(‘; { если і равно количеству элементов множества, то нам не нужны скобки в начале(их договорились опустить)}
Whilesumidobegin{пока количество элементов в новом понятиименьше размерности подзадачи, выполнить}
Pot^.next^.s:=pot^.next^.s+str1[k1]^.s;{добавить в понятие подпонятие с номером k1}
Sum:=sum+str1[k1]^.p;{добавить размерность, добавленного подпонятия}
Inc(k1);{увеличить k1 на 1}
End;
If(sum>i)or(k1=2) thenbegin{если количество элементов полученного понятия больше размерностизадачи или k1=2, то есть добавлено только одно понятие вподпонятие, то, чтобы избежать лишних скобок и неправильных решений выполнить}
Dispose(pot^.next); {освободить память, занимаемую этим«неправильным» понятием}
Pot^.next:=nil;{указать, что предыдущее понятие было последним}
Ifk1=2thenbreak{еслиk1=2, то выйти из основного цикла программы}
End
Elsebegin
Ifi=POWthenbegin {еслиразмерность текущей подзадачи равна размерности основной задачи, то}
Writeln(fil, pot^.next^.s);{записать понятие в файл}
Writeln(pot^.next^.s); {и вывести на экран}
Dispose(pot^.next); {освободить память, занимаемую понятием, так как понятия размерности задачи намбільше не понадобятся}
Pot^.next:=nil
End
Elsebegin{иначе инициализируем понятие до конца}
Pot:=pot^.next;
Pot^.s:=pot^.s+’)’; {закрываемскобку}
Pot^.next:=nil; {указываем, что это понятие последнее в списке}
Pot^.p:=I{указываем количество элементов, содержащихся в понятии}
End
End;
Forj:=k1-1downto2 dobegin{k1 сейчас показывает количество подпонятий последнегопонятия плюс 1. Поэтому в этом цикле, который попытается определить следующуюкомбинацию понятий и используется переменная k1.Эта часть программы рассматривает случай, когда подпонятия будут ставать неследующими по списку подпонятиями (по крайней мере не все), а будут происходитьдругие переходы. То есть этот цикл рассчитан на то, чтобы не позволитьподпонятию с большим номером по списку в понятии быть большим по абсолютномуадресу (по времени создания)}
If (str1[j]^.next=str1[j-1]) and (str1[j+1]=str1[j])or ((j=k1-1) and (str1[j]
Str1[j-1])) thenbegin{если за подпонятием с номером jпо списку следует подпонятие сномером j-1 и подпонятия с номером jи j+1совпадают, или jравно количеству подпонятий и последние два понятия совпадают(сравнение идет по абсолютным адресам расположения понятий в памяти), то}
str1[j]:=str1[j]^.next; {подпонятие сномером jпереходит на следующее за списком подпонятие}
Forj:=J+1tok1-1 dostr1[j]:=f;{а все следующие подпонятия, становятся равными первому (элементарному)подпонятию}
gotomet{хотя применение оператора безусловного перехода считается плохимстилем программирования, но здесь он оправдан, дабы не запутывать программуновыми циклами}
End;
End;
Forj:=k1-1downto2 dobegin{новый цикл, который переключит соответствующие подпонятия. Мы выделяем этов новый цикл, так как нужно было проверить на наличие “граничных” переходов(см. предыдущий цикл)}
Ifstr1[j]str1[j-1]thenbegin{если подпонятия с номерами jи (j-1) не совпадают, то}
Str1[j]:=str1[j]^.next; {подпонятие сномером jстановится следующим по списку (времени созданияподпонятием)}
Forj:=j+1tok1 dostr1[j]:=f;{а все идущие за ним подпонятия в списке подпонятий, составляющих понятиестановятся элементарными}
gotomet{выходим из цикла}
End
End;
Str1[1]:=str1[1]^.next; {если не выполнились условия предыдущих двухциклов, то пора переключать первое подпонятие}
forj:=2 toidostr1[j]:=f;{и, соответствено, следующиеподпонятия сделать элементарными}
Met: end
End;
Close(fil);{закрытьфайл}
Repeat {и}
Pot:=f^.next;
Dispose(f); {освободить память, занимаемую списком всехвозможных подпонятий}
F:=pot
Until fnil
end.Литература
1. В. Липский, Комбинаторика дляпрограммистов, пер. с польского, М. – Мир,1988