Комбинаторные алгоритмы

В этом разделе мы рассмотрим три наиболее важные задачи комбинаторики: нахождение всех подмножеств множества из n элементов; нахождение всех выборок по m элементов из n элементов и нахождение всех перестановок n элементов. Не умаляя общности, можно считать, что элементами множества являются натуральные числа от 1 до n. Решим первую задачу: найти (программа будет просто выводить их на экран) все подмножества множества {1..n}, где n - заданное натуральное число. Пусть, например, n=3, тогда решением задачи будет последовательность множеств {} (пустое множество), {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} - всего 2ⁿ различных подмножеств. Можно предложить такой алгоритм: начнем с пустого множества, добавим к нему последовательно элементы 1, 2, 3. Теперь к каждому множеству из одного элемента будем добавлять еще один элемент, а чтобы избежать повторений, будем добавлять только элементы, большие, чем максимальный элемент этого подмножества, таким способом получим подмножества {1,2}, {1,3} и {2,3}. Сделаем еще один шаг - будем добавлять еще по одному элементу к каждому двухэлементному подмножеству, в нашем примере это удастся сделать только с подмножеством {1,2}, получая трехэлементные подмножества, и так далее, пока все подмножества не будут получены. Этот алгоритм очень просто записать рекурсивной процедурой:

 

Procedure SubSets_Recursive(n,Last:Byte; S:T_Set);

{n - количество элементов, Last - наибольший элемент в текущем подмножестве, S - само это подмножество}

Var i : Byte;

Begin

If i In S Then Write(i);

WriteLn;

For i:=Last+1 To n Do {добавляем к S последовательно еще один элемент и углубляемся в рекурсию}

SubSets_Recursive(n,i,S+[i]);

End;

 

Первое обращение к этой процедуре следует записать в виде:

 

SubSets_Recursive(n,0,[]);

 

Известен и другой, нерекурсивный, алгоритм решения этой задачи, который также весьма прост. Множество {1...n} имеет 2ⁿ различных подмножеств, но 2ⁿ различных значений имеют и n-битовые двоичные числа (от 0 до 2ⁿ-1). Можно ли установить взаимно однозначное соответствие между всеми подмножествами и всеми числами от 0 до 2ⁿ-1? Можно - число 0, состоящее только из нулевых битов, соответствует пустому множеству, число 1 - множеству {1}, число 2 - множеству {2}, число 3 - множеству {1,2} (конечно, не {3}) и так далее, и наконец, число 2ⁿ-1, состоящее из единичных битов, соответствует полному множеству. Единичный k-й бит числа означает присутствие в множестве числа k+1, а нулевой бит - его отсутствие. Таким образом, задачу можно решить всего одним циклом; будем перебирать все числа от 0 до 2ⁿ-1 и для каждого из них выводить соответствующее множество, а распаковка двоичного числа - задача вполне тривиальная:

 

Procedure SubSets_Binary(n:Byte);

Var

i,Max,t : LongInt;

Count : Byte;

Begin

Max:=LongInt(1) ShL n-1; {вычислили 2^n-1}

For i:=0 To Max Do Begin

t:=i;

Count:=0;

{элемент, соответствующий очередному биту числа t}

While t>0 Do Begin

Inc(Count);

If t And 1=1 Then Write(Count);

{бит единичный, следовательно, число Count есть в подмножестве}

t:=t ShR 1;

End;

WriteLn;

End;

End;

 

Большинство задач комбинаторики, как и рассмотренная выше, допускает и рекурсивное и нерекурсивное решение. Теперь обратимся ко второй задаче: для заданных n и m (m£n) получить все подмножества множества {1...n}, содержащие ровно m элементов. Ее можно решить тем же самым рекурсивным алгоритмом, что и первую задачу, необходимо только прекращать рекурсию, когда количество элементов множества достигнет m, и не выводить меньшие множества :

Procedure Sized_Subsets_Recursive(n,m,Last,Size:Byte; S:T_Set);

{новый параметр Size - это размер текущего подмножества}

Var i : Byte;

Begin

If Size=m Then Begin {подмножество имеет нужный размер}

For i:=1 To n Do

If i In S Then Write(i);

Exit; {прекращаем рекурсию}

End;

For i:=Last+1 To n Do

Sized_Subsets_Recursive(n,m,i,Size+1,S+[i]);

End;

 

Первое обращение к этой процедуре записывается в виде

 

SubSets_Recursive(n,m,0,0,[]);

 

Такой алгоритм не вполне эффективен - он перебирает все подмножества размером меньше m, которые, вообще говоря, нас не интересуют (в первой задаче он не выполнял никаких лишних действий). Попробуем записать нерекурсивный алгоритм. Несколько модифицированная процедура SubSets_Binary годится, но она также будет неэффективной - подмножеств размера m существенно меньше, чем 2ⁿ, и алгоритм будет выполнять много лишних действий. Запишем более эффективный алгоритм. В этой задаче установить взаимно однозначное соответствие между искомыми подмножествами и отрезком ряда натуральных чисел не удается, попробуем решить ее несколько другим способом. Пусть по-прежнему каждое подмножество кодируется n-битовым двоичным числом, в котором единичный бит означает присутствие элемента. Тогда каждое из этих чисел будет содержать ровно m единичных битов. Наименьшее из чисел равно 00...011...1 и наибольшее 11...100...0. Будем получать эти числа в лексикографическом порядке. Найдем самую правую пару битов 01 , если такой пары нет, то это максимальное число и алгоритм завершен. Пусть номер нулевого бита в этой паре равен s, получим число, непосредственно следующее за данным, - заменим s-й бит на единичный, а s+1-й на нулевой (баланс единичных и нулевых битов не нарушится), а биты начиная с s+2-го переставим так, чтобы сначала шли все нулевые, а затем все единичные биты. Например, для n=4, m=2 алгоритм даст числа 0011, 0101, 0110, 1011, 1101, 1110. В программе будем для наглядности хранить каждый бит в отдельном элементе массива.

 

Var

x : Array[1..100] Of 0..1;

Last : Boolean;

i,p,s,num : Word;

Begin

{Получим и выведем подмножество, соответствующее начальной последовательности : 0...01...1}

For i:=1 To n-m Do x[i]:=0;

For i:=n-m+1 To n Do x[i]:=1;

For i:=n DownTo 1 Do

If x[i]=1 Then Write(n+1-i);

WriteLn;

{Получим все остальные подмножества}

While True Do Begin

{Найдем самую правую пару 01, если такой пары нет, то последовательность имеет вид 11...10...0 и генерация завершена}

s:=n-1;

While (s>0) And Not ((x[s]=0) And (x[s+1]=1)) Do Dec(s);

If s=0 Then Break;

num:=0;

{num - число единиц в подпоследовательности x[s+2]...x[n]}

For i:=s+2 To n Do Inc(num,x[i]);

x[s]:=1; {x[s] меняем с 0 на 1}

For i:=s+1 To n-num Do x[i]:=0;

{после s записываем нужное количество нулей}

For i:=n-num+1 To n Do x[i]:=1;

{в хвост записываем num единиц}

For i:=n DownTo 1 Do {выводим очередное подмножество}

If x[i]=1 Then Write(n+1-i);

WriteLn;

End;

End;

 

В третьей задаче требуется получить все возможные перестановки элементов {1...n}, причем порядок элементов в перестановке важен, так что задача не сводится к предыдущей. Так для n=3 решением будут перестановки 123, 132, 213, 231, 312, 321. Всего перестановок n!, и следовательно, эта задача сложнее, чем две предыдущие. Но рекурсивный алгоритм, использованный нами в задачах 1 и 2, годится с небольшими изменениями и здесь. Будем получать перестановки в следующей последовательности: сначала перестановка пуста, затем последовательно будем записывать в нее элементы 1,2,...,n, затем к каждой перестановке из одного элемента будем дописывать последовательно все элементы 1,2,...,n, кроме того элемента, который там уже есть. Все эти перестановки будут промежуточными результатами, пока там не окажутся все n элементов. Запишем этот алгоритм в виде рекурсивной процедуры.

 

Procedure Replacing_Recursive(n,Size:Byte; Var x:T_Array; Rest:T_Set);

{процедура получает Size - количество элементов в перестановке, x - текущую перестановку (она хранится в числовом массиве), Rest - множество элементов, не входящих в перестановку x}

Var i : Byte;

Begin

If Size=n Then Begin

{полная перестановка получена, выведем ее и прекратим рекурсию}

For i:=1 To n Do Write(x[i]);

WriteLn;

Exit;

End;

For i:=1 To n Do

If i In Rest Then Begin {элемент i еще не использован}

x[Size+1]:=i; {добавим его в перестановку}

Replacing_Recursive(n,Size+1,x,Rest-[i]);

{размер перестановки увеличился на 1, а элемент i исключен из множества неиспользованных элементов}

End;

End;

 

Эту процедуру необходимо вызывать в виде:

 

Var r : T_Array;

Begin

Replacing_Recursive(n,0,,r,[1..n]);

End.

 

Данный рекурсивный алгоритм так же, как в задаче 2, не очень эффективен, так как он собирает каждую перестановку по одному элементу. Нельзя ли записать более эффективный алгоритм? В задаче 2 мы перечислили в лексикографическом порядке все последовательности из m единиц и n-m нулей. Здесь нам нужно сделать почти то же самое - перечислить в лексикографическом порядке последовательности из чисел 1,2,...,n, в которые каждое число входит по одному разу. Будем хранить последовательности в массиве X. В качестве начальной последовательности возьмем последовательность 1,2,3,...,n. Чтобы получить следующую последовательность из предыдущей, найдем самый правый элемент X[p] - такой, что X[p]<X[p+1], если такого не окажется, значит последовательность имеет вид n,...,2,1 и это последняя из перестановок. Затем среди элементов X[p+1],X[p+2],...,X[n] найдем наименьший элемент X[q], больший, чем X[p], поменяем местами элементы X[p] и X[q] и инвертируем подпоследовательность X[p+1],X[p+2],...,X[n]. Новая перестановка получена. Этот алгоритм гораздо эффективнее, так как не рассматривает никаких подмножеств, кроме n-элементных, каждое из которых входит в решение.

 

Procedure Replacing_Lexicographic(n:Byte);

Var

x : T_Array;

i,p,q,min,tmp : Byte;

Begin

For i:=1 To n Do x[i]:=i;

For i:=1 To n Do Write(x[i]);

WriteLn;

While True Do Begin

{ Ищем самый правый элемент X[p] - такой, что X[p]<X[p+1]. Если такого элемента нет, то все перестановки уже получены }

p:=n-1;

While (p>0)And(x[p]>x[p+1]) Do Dec(p);

If p=0 Then Break;

{Среди элементов X[p+1],X[p+2],...,X[n] ищем наименьший элемент X[q],больший,чем X[p]}

min:=n+1;

For i:=p+1 To n Do

If (x[i]>x[p])And(x[i]<min) Then Begin

min:=x[i];

q:=i;

End;

{ Меняем местами элементы X[p] и X[q] }

tmp:=x[p];

x[p]:=x[q];

x[q]:=tmp;

{ Инвертируем подпоследовательность X[p+1],X[p+2],...,X[n] }

For i:=1 To (n-p) Div 2 Do Begin

tmp:=x[p+i];

x[p+i]:=x[n+1-i];

x[n+1-i]:=tmp;

End;

For i:=1 To n Do Write(x[i]); WriteLn;

End;

End;

 

Рекурсивные алгоритмы, использованные нами для решения всех трех задач, очень похожи, по сути это один и тот же алгоритм, основанный на обходе всего дерева решений. Дерево решений для этого класса задач - это дерево, в корне которого содержится пустая последовательность, в вершинах первого уровня - последовательности из одного элемента, в вершинах второго уровня - последовательности из двух элементов и так далее, и листьями дерева являются последовательности, содержащие все элементы от 1 до n. Конечно, мы не осуществляли полный обход дерева, например, из всех листьев в задачах 1 и 2 достаточно было посетить только один. Все такие алгоритмы имеют общее название - метод ветвей и границ - и широко применяются в программировании.