Комбинаторные алгоритмы решения школьных задач по информатике

Генерация k-элементных подмножеств

В комбинаторике такие  подмножества называют сочетаниями  из n элементов по k элементов и обозначают C_n^k . Их количество выражается следующей формулой:

Однако при программировании гораздо удобнее использовать следующие  рекуррентные соотношения:

Объясняется это тем, что в формуле (1) числитель и  знаменатель растут очень быстро, поэтому в силу особенностей компьютерной арифметики не всегда возможно точно вычислить значение C_n^k, даже когда последнее не превосходит максимально представимое целое число.

При фиксированном значении n максимального значения число сочетаний достигает при k = n/2 (вернее, для четного n максимум один и он указан, а для нечетного — максимум достигается на двух соседних значениях k: [n/2] и [n/2]+1). Поэтому особенно полезной оказывается следующая оценка для четных n[4] (очевидно, что при нечетных n отличия будут минимальными), основанная на формуле Стирлинга:

Если допустить, что  за время, отведенное для решения  задачи, мы можем перебрать около 10⁶ вариантов, то из формулы (3) следует, что генерацию всех сочетаний из n элементов для любого фиксированного k можно проводить для n £ 24.

Обычно генерацию всех k-элементных подмножеств проводят в лексикографическом порядке, тем более что в данном случае это не приводит ни к усложнению алгоритма, ни к увеличению его вычислительной трудоемкости. Напомним, что порядок подмножеств называется лексикографическим, если для любых двух подмножеств справедливо, что раннее должно быть сгенерировано то из них, из индексов элементов которого можно составить меньшее k-значное число в n-ричной системе счисления (или в десятичной, для n < 10). Так, для n = 6 и k = 3 сочетание из третьего, первого и пятого элемента должно быть сгенерировано раньше, чем из второго, третьего и четвертого, так как 135 < 234.

Рассмотрим рекурсивный  алгоритм решения данной задачи. Идея сведения данной задачи к задаче меньшей  размерности следующая. Первым элементом подмножества может быть любой элемент, начиная с первого и заканчивая (n – k + 1)-м элементом. После того, как индекс первого элемента подмножества зафиксирован, осталось выбрать k – 1 элемент из элементов с индексами, большими, чем у первого. Далее поступаем аналогично. Когда выбран последний элемент, то мы достигли конечного уровня рекурсии и выбранное подмножество можно обработать (проанализировать или распечатать). В предлагаемой ниже программе массив a содержит значения элементов исходного множества и может быть заполнен произвольным образом. В массиве p будем формировать очередное сочетание из k элементов.

const nmax = 24;

type list = array[1..nmax] of integer;

var k,i,j,n,q : integer;    

a,p : list;

procedure print(k : integer);

var i:integer;

begin  

for j:=1 to k do    

write(p[j]:4);  

writeln

end;{print} 

 

procedure cnk(n,k : integer); 

 

 

 procedure gen(m,L : integer); 

var i:integer; 

begin   

if m=0 then print(k) else     

for i:=L to n-m+1 do       

begin         

p[k-m+1]:=a[i];         

gen(m-1,i+1)       

end 

end;{gen} 

 

begin {cnk}  

gen(k,1)

end;{cnk} 

begin {main}  

readln(n,k);  

for i:=1 to n do    

a[i]:=i;{заполнить массив  можно и по-другому}  

cnk(n,k)

end.

Заметим, что собственно генерация сочетаний производится в рекурсивной подпрограмме gen. Она имеет следующие параметры: m - сколько элементов из множества нам еще осталось выбрать и L - начиная с какого элемента исходного множества, следует выбирать эти m элементов. Обратите внимание, что именно вложенная структура описания процедур cnk и gen позволяет не передавать при рекурсивных вызовах значения n и k, а из основной программы обращаться к процедуре cnk с параметрами, соответствующими постановке задачи, не вдаваясь в подробности ее решения. Такой способ будем применять и в дальнейшем.

6.2. Нумерация подмножеств

Генерация всех подмножеств данного множества

При решении олимпиадных  задач чаще всего заранее неизвестно, сколько именно элементов исходного  множества должно входить в искомое  подмножество, то есть необходим перебор всех подмножеств. Однако, если требуется найти минимальное подмножество, то есть состоящее как можно из меньшего числа элементов (или максимальное подмножество), то эффективнее всего организовать перебор так, чтобы сначала проверялись все подмножества, состоящие из одного элемента, затем из двух, трех и т. д. элементов (для максимального подмножества — в обратном порядке). В этом случае, первое же подмножество, удовлетворяющее условию задачи и будет искомым и дальнейший перебор следует прекратить. Для реализации такого перебора можно воспользоваться, например, процедурой cnk, описанной в предыдущем разделе. Введем в нее еще один параметр: логическую переменную flag, которая будет обозначать, удовлетворяет текущее сочетание элементов условию задачи или нет. При получении очередного сочетания вместо его печати обратимся к процедуре его проверки check, которая и будет определять значение флага. Тогда начало процедуры gen следует переписать так:

procedure gen(m,L:integer);

var i:integer;

begin  

if m=0 then    

begin      

check(p,k,flag);      

if flag then exit    

end  

else ...

Далее процедура дословно совпадает с предыдущей версией. В основной же программе единственное обращение к данной процедуре  следует заменить следующим фрагментом:

k:=0;

flag:=false;

repeat  

k:=k+1;  

cnk(n,1,flag)

until flag or (k=n);

if flag then print(k)

else writeln('no solution');

Очевидно также, что  в основной программе запрос значения переменной k теперь не производится.

Существует также альтернативный подход к перебору всех подмножеств того или иного множества. Каждое подмножество можно охарактеризовать, указав относительно каждого элемента исходного множества, принадлежит оно данному подмножеству или нет. Сделать это можно, поставив в соответствие каждому элементу множества 0 или 1. То есть каждому подмножеству соответствует n-значное число в двоичной системе счисления (строго говоря, так как числа могут начинаться с произвольного количества нулей, которые значащими цифрами не считаются, то следует заметить, что в соответствие ставятся n-или менее -значные числа). Отсюда следует, что полный перебор всех подмножеств данного множества соответствует перебору всех чисел в двоичной системе счисления.

 Теперь легко подсчитать  и количество различных подмножеств  данного множества. Оно равно 2ⁿ – 1 (или 2ⁿ, с учетом пустого множества). Таким образом, сопоставляя два способа перебора всех подмножеств данного множества, мы получили следующую формулу: 

То есть, в рамках сделанной  выше оценки на количество допустимых вариантов в переборе, мы можем рассмотреть все подмножества исходного множества только при n £ 20.

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

Условие. Дан целочисленный массив a[1..N] (N £ 20) и число M. Найти подмножество элементов массива a[i1], a[i2], ...a[ik] такое, что 1 £ i1 < i2 < i3 < ... < ik £ N и a[i1] + a[i2] + ... + a[ik] = M.

Решение. В качестве решения приведем процедуру генерации всех подмножеств, которые можно составить из элементов массива и функцию проверки конкретного подмножества на соответствие условию задачи.

function check(j:longint):boolean;

var k:integer; s:longint;

begin  

s:=0;  

for k:=1 to n do    

if ((j shr (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);

var q,j:longint;

begin  

q:=1 shl n; {таким образом мы помещаем в q число 2^n}  

for j:=1 to q-1 do {цикл по всем подмножествам}     

if check(j) then exit

end;

Заметим, что если все  элементы в массиве положительные, то, изменив порядок рассмотрения подмножеств, решение приведенной  выше задачи можно сделать более эффективным. Так, если сумма элементов какого-либо подмножества уже больше, чем M, то рассматривать подмножества, включающие его в себя уже не имеет смысла. Пересчет же сумм можно оптимизировать, если каждое следующее сгенерированное подмножество будет отличаться от предыдущего не более, чем на один элемент.

Приведенная же программа чрезвычайно проста, но обладает одним недостатком: мы не можем ни в каком случае с ее помощью перебирать все подмножества множеств, состоящих из более, чем 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.

6.3. Скобочные последовательности и их нумерация

Определение:

Скобочная последовательность — класс комбинаторных объектов, представляющих собой последовательность скобочных символов.

Примеры скобочных  последовательностей:

Определение:

Правильная  скобочная последовательность — частный случай скобочной последовательности, определяющийся следующими образами: "" (пустая строка) есть правильная скобочная последовательность; пусть   — правильная скобочная последовательность, тогда   есть правильная скобочная последовательность; пусть  ,   — правильные скобочные последовательности, тогда   есть правильная скобочная последовательность;

Примеры правильных скобочный последовательностей:

Алгоритм проверки правильности скобочной последовательности

Пусть нам дана скобочная  последовательность, записанная в строку  . Возьмем переменную  ,  . Будем последовательно перебирать все символы этой строки. Если мы встречаем открывающуюся скобку, то увеличиваем   на  , закрывающую — уменьшаем на  . Если на протяжении всего перебора   было неотрицательным и после завершения осталось нулем, то скобочная последовательность правильна.