Рефераты. Некоторые способы разбиения множеств

Некоторые способы разбиения множеств

Введение

В наш бурно развивающийся век, казалось бы, все алгоритмы, которые можно придумать, уже придуманы. Но иногда встречаются задачи, для которых нет подходящих алгоритмов. Быть может потому, что задача редко встречается или, скорее всего для этой задачи нет эффективных алгоритмов (а, скорее всего, их и вовсе не существует).

В этой работе будет обсуждаться тема разбиений множеств.

В [1] автор даёт несколько таких алгоритмов: генерирование всех подмножеств n-элементного множества, генерирование всех k-элементных подмножеств множества {1, …, n} в лексикографическом порядке, генерирование всех разбиений множества {1, …, n} (на этом алгоритме остановимся подробней), нахождение всех разбиений числа.

Первый из этих алгоритмов использует идею бинарного кода Грэя, остальные основаны на удалении или добавлении одного элемента. Последний алгоритм использует схему разбиения большего числа на меньшие числа.

Постановка задачи

Формулировка первой задачи, которую мы рассмотрим, выглядит так: необходимо сгенерировать все разбиения множества, содержащего n элементов.

Для формулировки второй задачи необходимо ввести некоторые понятия.

Итак, дано множество, состоящее из n элементов. Каждый элемент этого множества образует некоторое понятие. Два или больше понятия могут быть объединены в новое понятие. Отличительная черта понятий - взятие их в круглые скобки.

Задача выглядит так: сгенерировать все понятия, которые могут быть образованы из n элементов. Например, для n=3 имеем такие понятия (круглые скобки в начале и в конце опущены для краткости): (*)**, (*)(*)*, (*)(*)(*), (**)*, (**)(*), ((*)*)*, ((*)*)(*), ((*)(*))*, ((*)(*))(*).

Математическое обоснование

Под разбиением n-элементного множества Х на k блоков будем понимать произвольное семейство , такое, что для 1і<jk и для 1ik. Подмножества будем называть блоками семейства р. Множество всех разбиений множества Х на 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<k<n, (1)

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).

Теперь опишем алгоритм генерирования всех разбиений множества.

Отметим, что каждое разбиение множества {1,…, n} однозначно определяет разбиение множества {1,…,n-1}, возникшее из после удаления элемента 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]of boolean;

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 then write(i, ' '); {если число і из блока j, то пишем это число}

j:=sled[j]; {следующий по номеру блок}

write(')');

until j=0;

WRITELN

end;

begin

write('input n:');

readln(n); {вводим количество элементов множества}

for i:=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 then sled[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(not wper[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 - будет содержать ссылки на каждое понятие в составном понятии;

program dyscretics_optimisation(input,output);

Страницы: 1, 2



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.