Порождение и перебор комбинаторных объектов

Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе ВСЕХ возможных вариантов и сравнении их между собой. Поэтому так важно для нас научиться строить алгоритмы ПЕРЕБОРА различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д.

Схема перебора всегда будет одинакова:

- во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);

- во-вторых, научиться переходить от произвольного элемента к HЕПОСРЕДСТВЕHHО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).

Hаиболее естественным способом упорядочения составных объектов является ЛЕКСИКОГРАФИЧЕСКИЙ порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать за- ново. Пока запишем схему перебора в таком виде:

X:=First;

while X<>Last do Next(X);

где First - первый элемент; Last - последний элемент; Next - процедура получения следующего элемента.

Последовательности

Hапечатать все последовательности длины N из чисел 1,2,...,M.

 

First = (1,1,...,1) Last = (M,M,...,M)

Всего таких последовательностей будет M^N (докажите!). Чтобы понять. как должна действовать процедура Next, начнем с примеров. Пусть N=4,M=3. Тогда:

Next(1,1,1,1) -> (1,1,1,2) Next(1,1,1,3) -> (1,1,2,1) Next(3,1,3,3) -> (3,2,1,1)

Теперь можно написать общую процедуру Next:

procedure Next; begin {найти i: X[i]<M,X[i+1]=M,...,X[N]=M}; X[i]:=X[i]+1; X[i+1]:=...:=X[N]:=1

end;

Если такого i найти не удается, то следующей последовательности нет - мы добрались до последней (M,M,...,M). Заметим также, что если бы членами последовательности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа на Паскале выглядит так:

program Sequences; type Sequence=array [byte] of byte; var M,N,i:byte; X:Sequence; Yes:boolean; procedure Next(var X:Sequence;var Yes:boolean); var i:byte; begin i:=N; {поиск i} while (i>0)and(X[i]=M) do begin X[i]:=1;dec(i) end; if i>0 then begin inc(X[i]);Yes:=true end else Yes:=false end; begin write('M,N=');readln(M,N); for i:=1 to N do X[i]:=1; repeat for i:=1 to N do write(X[i]);writeln; Next(X,Yes) until not Yes

end.

Перестановки

Hапечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).

 

First = (1,2,...,N) Last = (N,N-1,...,1)

Всего таких перестановок будет N!=N*(N-1)*...*2*1 (докажите!). Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X[i+1]>...>X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],...,X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,...,N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

procedure Next; begin {найти i: X[i]<X[i+1]>X[i+2]>...>X[N]}; {найти j: X[j]>X[i]>X[j+1]>...>X[N]}; {обменять X[i] и X[j]}; {X[i+1]>X[i+2]>...>X[N]}; {перевернуть X[i+1],X[i+2],...,X[N]};

end;

Теперь можно написать программу:

program Perestanovki; type Pere=array [byte] of byte; var N,i,j:byte; X:Pere; Yes:boolean; procedure Next(var X:Pere;var Yes:boolean); var i:byte; procedure Swap(var a,b:byte); {обмен переменных} var c:byte; begin c:=a;a:=b;b:=c end; begin i:=N-1; {поиск i} while (i>0)and(X[i]>X[i+1]) do dec(i); if i>0 then begin j:=i+1; {поиск j} while (j<N)and(X[j+1]>X[i]) do inc(j); Swap(X[i],X[j]); for j:=i+1 to (N+i) div 2 do Swap(X[j],X[N-j+i+1]); Yes:=true end else Yes:=false end; begin write('N=');readln(N); for i:=1 to N do X[i]:=i; repeat for i:=1 to N do write(X[i]);writeln; Next(X,Yes) until not Yes end.

Разбиения

Перечислить все разбиения целого положительного числа N на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно).

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

First = (1,1,...,1) - N единиц Last = (N)

 

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см.следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?

Во-первых, должно быть X[i-1]>X[i] или i=1. Во-вторых, i должно быть не последним эле ментом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие элементы надо взять минимально возможными, т.е. равными единице:

procedure Next; begin {найти i: (i<L) and ((X[i-1]>X[i]) or (i=1))} X[i]:=X[i]+1; { L:= i + X[i+1]+...+X[L] - 1 } X[i+1]:=...:=X[L]:=1

end;

Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1<=L<=N). Программа будет выглядеть так:

program Razbieniya; type Razb=array [byte] of byte; var N,i,L:byte; X:Razb; procedure Next(var X:Razb;var L:byte); var i,j:byte; s:word; begin i:=L-1;s:=X[L]; {поиск i} while (i>1)and(X[i-1]<=X[i]) do begin s:=s+X[i];dec(i) end; inc(X[i]); L:=i+s-1; for j:=i+1 to L do X[j]:=1 end; begin write('N=');readln(N); L:=N; for i:=1 to L do X[i]:=1; for i:=1 to L do write(X[i]);writeln; repeat Next(X,L); for i:=1 to L do write(X[i]);writeln until L=1 end.

Подсчет количеств

Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C(n,k) - число всех k-элементных подмножеств n-элементного множества - можно найти, заполняя таблицу значений функции С по формулам:

C(n,0) = C(n,n) = 1 (n>=1) C(n,k) = C(n-1,k-1) + C(n-1,k) (n>1, 0<k<n);

или по формуле n!/(k!*(n-k)!) (первый способ эффективнее, если надо вычислить много значений С(n,k)).

Попробуем посчитать таким способом количество разбиений из пункта 1.3. Обозначим через R(N,k) (при N>=0, k>=0) число разбие- ний N на целые положительные слагаемые, не превосходящие k (при этом R(0,k) считаем равным 1 для всех k>=0). Очевидно, что число R(N,N) и будет искомым. Все разбиения N на слагаемые, не превосходящие k, разобьем на группы в зависимости от максимального слагаемого (обозначим его i).

Число R(N,k) равно сумме (по всем i от 1 до k) количеств разбиений со слагаемыми не больше k и максимальным слагаемым, равным i. А разбиения N на слагаемые не более k с первым слагаемым, равным i, по существу представляют собой разбиения n-i на слагаемые, не превосходящие i (при i<=k). Так что

R(N,k) = R(N-1,1)+R(N-2,2)+...+R(N-k,k).

Рекурсия

Вы уже знаете, что рекурсивными называются процедуры и функции, которые вызывают сами себя. Рекурсия позволяет очень просто (без использования циклов) программировать вычисление функций, заданных рекуррентно, например факториала f(n)=n!:

f(0)=1 f(n)=n*f(n-1).

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

Примечание: рекурсия, безусловно, весьма удобна, однако часто требует громадное количество ресурсов. В частности, программа для факториала на 7-мом десятке завесит самый быстрый Pentium - III+. Из-за времени выполнения. О том, как этого избежать, можно прочитать в статье Динамическое программирование.

Факториал

Еще раз напомним рекурсивный алгоритм вычисления факториала:

program Factorial; var N:word; function F(n:word):longint; begin if n=0 then F:=1 else F:=n*F(n-1) end; begin write('N=');readln(N); writeln('N!=',F(N)) end.

Ханойская башня

Игра "Ханойская башня" состоит в следующем. Есть три стержня. Hа первый из них надета пирамидка из N колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить программу, указывающую требуемые действия.

 

Hапишем рекурсивную процедуру перемещения M верхних колец с A-го стержня на B-ый в предположении, что остальные кольца больше по размеру и лежат на стержнях без движения:

procedure Move(M,A,B:integer); var C:integer; begin if M=1 then begin writeln ('сделать ход ',A,'->',B) end else begin C:=6-A-B; {C - третий стержень: сумма номеров равна 6} Move(M-1,A,C); Move(1,A,B); Move(M-1,C,B) end

end;

Сначала переносится пирамидка из M-1 колец на третий стержень C. После этого M-ое кольцо освобождается, и его можно перенести на B. Остается перенести пирамиду из N-1 кольца с C на B. Чем это проще первоначальной задачи? Тем, что количество колец стало на единицу меньше. Теперь основную программу можно записать в несколько строк:

program Hanoi; var N:integer; procedure Move(M,A,B:integer);............. begin write('N=');readln(N); Move(N,1,2)

end.

Если вы владеете основами компьютерной графики, можете попробовать "нарисовать" каждый ход на экране.

Таким образом, ОСHОВHАЯ ИДЕЯ любого рекурсивного решения - свести задачу к точно такой же, но с меньшим значением параметра. При этом какое-то минимальное значение параметра (например, 1 или 0) должно давать решение без рекурсивного вызова - иначе программа "зациклится" (последовательность рекурсивных вызовов будет бесконечной). Это напоминает метод математической индукции в математике. В некоторых задачах удобно наоборот, увеличивать значение параметра при рекурсивном вызове. Тогда, естественно, "безрекурсивное" решение должно предусматриваться для некоторого максимального значения параметра. Попробуем использовать эту идею для перебора комбинаторных объектов.