Комбинаторные задачи (стр. 2 из 3)
Решение. В качестве решения приведем процедуру генерации всех подмножеств, которые можно составить из элементов массива и функцию проверки конкретного подмножества на соответствие условию задачи.
function check(j:longint):boolean;
var k:integer; s:longint;
begin
s:=0;
fork:=1 tondo
if ((jshr (k-1))and 1)=1 {данное условие означает, что в
k-й справа позиции числа j, в 2-й системе, стоит 1}
then s:=s+a[k];
if s=m then
begin
for k:=1 to n do
if ((j shr (k-1))and 1)=1 then write(a[k]:4);
writeln
end
end;
procedure subsets(n:integer);
varq,j:longint;
begin
q:=1 shln; {таким образом мы помещаем в q число 2^n}
forj:=1 toq-1 do {цикл по всем подмножествам}
if check(j) then exit
end;
Заметим, что если все элементы в массиве положительные, то, изменив порядок рассмотрения подмножеств, решение приведенной выше задачи можно сделать более эффективным. Так, если сумма элементов какого-либо подмножества уже больше, чем M, то рассматривать подмножества, включающие его в себя уже не имеет смысла. Пересчет же сумм можно оптимизировать, если каждое следующее сгенерированное подмножество будет отличаться от предыдущего не более, чем на один элемент (такой способ перечисления подмножеств показан в [2]). Приведенная же программа черезвычайно проста, но обладает одним недостатком: мы не можем ни в каком случае с ее помощью перебирать все подмножества множеств, состоящих из более, чем 30 элементов, что обусловлено максимальным числом битов, отводимых на представление целых чисел в Турбо Паскале (32 бита). Но, как уже было сказано выше, на самом деле, перебор всех подмножеств у множеств большей размерности вряд ли возможен за время, отведенное для решения той или иной задачи.
Генерация всех перестановок n-элементного множества
Количество различных перестановок множества, состоящего из n элементов равно n!. В этом нетрудно убедиться: на первом месте в перестановке может стоять любой из n элементов множества, после того, как мы на первом месте зафиксировали какой-либо элемент, на втором месте может стоять любой из n – 1 оставшегося элемента и т.д. Таким образом, общее количество вариантов равно n(n– 1)(n– 2)...3×2×1 = n!. То есть рассматривать абсолютно все перестановки мы можем только у множест, состоящих из не более, чем 10 элементов.
Рассмотрим рекурсивный алгоритм, реализующий генерацию всех перестановок в лексикографическом порядке. Такой порядок зачастую наимболее удобен при решении олимпиадных задач, так как упрощает применение метода ветвей и границ, который будет описан ниже. Обозначим массив индексов элементов — p. Первоначально он заполнен числами 1, 2, ..., n, которые в дальнейшем будут меняться местами. Параметром i рекурсивной процедуры Perm служит место в массиве p, начиная с которого должны быть, получены все перестановки правой части этого массива. Идея рекурсии, в данном случае следующая: на i-ом месте должны побывать все элементы массива p с i-го по n-й и для каждого из этих элементов должны быть получены все перестановки остальных элементов, начиная с (i+1)-го места, в лексикографическом порядке. После получения последней из перестановок, начиная с (i+1)-го места, исходный порядок элементов должен быть восстановлен.
{описание переменных совпадает с приведенным выше}
procedure Permutations(n:integer);
procedure Perm(i:integer);
var j,k:integer;
begin
if i=n then
begin for j:=1 to n do write(a[p[j]],' '); writeln end
else
begin
for j:=i+1 to n do
begin
Perm(i+1);
k:=p[i]; p[i]:=p[j]; p[j]:=k
end;
Perm(i+1);
{циклический сдвиг элементов i..n влево}
k:=p[i];
for j:=i to n-1 do p[j]:=p[j+1];
p[n]:=k
end
end;{Perm}
begin {Permutations}
Perm(1)
end;
begin {Main}
readln(n);
for i:=1 to n do p[i]:=i;
a:=p; {массив a может быть заполнен произвольно}
Permutations(n)
end.
Заметим, что в данной программе массив p можно было и не использовать, а переставлять непосредственно элементы массива a.
Разбиения множества
Число разбиений n-элементного множества на k блоков произвольного размера, но таких, что каждый элемент множества оказывается “приписан” к одному из блоков, выражается числом Стирлинга второго рода S(n,k) [6,7]. Очевидно, что S(n,k) = 0 для k> n. Если согласиться, что существует только один способ разбиения пустого множества на нулевое число непустых частей, то S(0,0) = 1 (именно такая договоренность, как и в случае с факториалом, приводит в дальнейшем к универсальным формулам). Так как при разбиении непустого множества нужна, по крайней мере, одна часть, S(n,0) = 0 при n> 0. Отдельно интересно также рассмотреть случай k = 2. Если непустое множество разделили на две непустые части, то в первой части может оказаться любое подмножество исходного множества, за исключением подмножеств, включающих в себя последний элемент множества, а оставшиеся элементы автоматически попадают во вторую часть. Такие подмножества можно выбрать 2n-1 – 1 способами, что и соответствует S(n,2) при n > 0.
Для произвольного k можно рассуждать так. Последний элемент либо будет представлять из себя отдельный блок в разбиении и тогда оставшиеся элементы можно разбить уже на k – 1 частей S(n– 1,k – 1) способами, либо помещаем его в непустой блок. В последнем случае имеется kS(n – 1,k) возможных вариантов, поскольку последний элемент мы можем добавлять в каждый блок разбиения первых n - 1элементов на k частей. Таким образом
S(n,k) = S(n – 1, k – 1) + kS(n – 1, k), n > 0. (5)
Полезными могут оказаться также формулы, связывающие числа Стирлинга с биномиальными коэффициентами, определяющими число сочетаний:
 |
Если же значение 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. На одном острове Новой Демократии каждый из его жителей организовал партию, которую сам и возглавил. Отметим, что к всеобщему удивлению даже в самой малочисленной партии оказалось не менее двух человек. К сожалению, финансовые трудности не позволили создать парламент, куда вошли бы, как предпологалось по Конституции острова, президенты всех партий. Посовещавшись, Островитяне решили, что будет достаточно, если в парламенте будет хотя бы один член каждой партии. Помогите Островитянам организовать такой, как можно более малочисленный парламент, в котором будут представлены члены всех партий.