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

Если же значение k теперь не фиксировать и рассмотреть все разбиения n-элементного множества, то их количество выражается числом Белла

По формулам (7) можно подсчитать, что в рамках принятых выше допущений можно построить все разбиения множества, состоящего не более чем из 15 элементов (B15=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);

write(' |') {блок напечатан}

end;

writeln {разбиение напечатано}

end;

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

Если при этом рассматривать массив p как n-значное число n-ричной системе счисления, то можно ввести понятие лексикографического порядка для разбиений множества и ставить задачи определения номера разбиения и обратную ей. Как и ранее (см. [1-3]), они решаются методом динамического программирования и не используют непосредственную генерацию всех разбиений.

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

Олимпиадные задачи, использующие комбинаторные конфигурации

Пример 1. На одном острове Новой Демократии каждый из его жителей организовал партию, которую сам и возглавил. Отметим, что к всеобщему удивлению даже в самой малочисленной партии оказалось не менее двух человек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предпологалось по Конституции острова, президенты всех партий. Посовещавшись, Островитяне решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии. Помогите Островитянам организовать такой, как можно более малочисленный парламент, в котором будут представлены члены всех партий.

Исходные данные: каждая партия и, соответственно, ее президент имеют одинаковый порядковый номер от 1 до N (4 £ N £ 150). Вам даны списки всех N партий Острова Новой Демократии. Выведите предлагаемый Вами парламент в виде списка номеров его членов. (Олимпиада стран СНГ, г. Могилев, 1992 г.)

Решение: с теоретической точки зрения, данная задача совпадает с задачей генерации всех подмножеств из множества жителей острова новой демократии. Причем наиболее подходящим кажется первый подход к решению данной задачи, связанный с генераций различных сочетаний, начиная с одного жителя. Для полноты изложения этого подхода, опишем функцию сheck, которую следует применить в данной задаче. Исходные данные следует записать в массив s:array[1 150] of set of 1 150, заполнив каждый из n первых элементов этого массива множеством тех партий, в которых состоит тот или иной житель. Тогда функция проверки сочетания из элементов этого массива примет следующий вид:

function check(var p:list;k:integer): boolean;

var i:integer; ss:set of 1 150;

begin

ss:=[];

for i:=1 to k do ss:=ss+s[p[i]];

check:=(ss=[1 n])

end;

Как видно из описания функции, использование типа “множество”, позволяет не только упростить данную программу, но и существенно ускорить ее выполнение, по сравнению с работой с массивами. Однако большая размерность данной задачи не позволяет считать приведенное решение удовлетворительным во всех случаях. Так, уже для n = 100, перебор всех сочетаний из 4-х и менее жителей приводит к рассмотрению около 4-х миллионов вариантов. Для построения кода, пригодного для решения данной задачи при любых входных данных, несколько изменим описание массива s:

s: array[1 150] of

record name,number:integer;

partys: set of 1 150

end;

Здесь поле partys совпадает по смыслу с первоначальным описанием массива s, поле name cоответствует номеру (то есть фактически имени) жителя и первоначально данное поле следует заполнить числами от 1 до n cогласно индексу элемента в массиве записей, и поле number соответствует количеству элементов во множестве из поля partys, то есть имеет смысл сразу подсчитать, в каком количестве партий состоит тот или иной житель. Теперь следует отсортировать массив s по убыванию значений поля number. Верхнюю оценку для числа членов парламента (kmax) подсчитаем, построив приближенное решение данной задачи следующим образом: во-первых, включим в парламент жителя, состоящего в максимальном количестве партий, затем исключим эти партии из остальных множеств и заново найдем в оставшемся массиве элемент с максимальным значением поля number (уже пересчитанного) и включим его в парламент, и так далее, до тех пор, пока сумма значений пересчитанных полей number у жителей, включенных в парламент, не будет равна n. Найденное количество членов парламента и будет kmax.

Теперь следует рассматривать сочетания из (kmax – 1) элемента, затем из (kmax – 2) и т. д. элементов. Если для сочетаний из какого-то рассматриваемого количества элементов k, решение найдено не будет, то это означает, что точным является решение с количеством членов парламента k+1. Так как массив s упорядочен, то, если решение для того или иного значения k существует, то, скорее всего, оно будет найдено при рассмотрении в лексикографическом порядке первых же сочетаний по k элементов. Поэтому временная трудоемкость в переборе возникает, только если решения c данным значением k не существует. В такой ситуации можно воспользоваться следующим “ненаучным” приемом: на поиск решения для каждого k, меньшего, чем kmax отведем фиксированное количество времени, скажем, 2-3 секунды (точнее данное время стоит определить экспериментальным путем). Если за отведенное время решение не найдено, то следует считать полный перебор невозможным и закончить выполнение программы. В любом случае, мы будем иметь какое-либо решение исходной задачи: точное или приближенное, то есть, возможно, содержащее больше членов парламента, чем минимально возможно. Однако, на практике такой подход почти всегда приводит к точному решению, в силу перебора “с предпочтением”, проводимого для каждого k (невозможность проведения полного перебора для какого-либо k на практике соответствует отсутствию решения для данного k).

 Скачать реферат