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

Здесь собраны задачи, в которых требуется получить один за другим все элементы некоторого множества.

2.1. Размещения с повторениями

2.1.1. Напечатать все последовательности длины k из чисел 1..n.

Решение. Будем печатать их в лексикографическом порядке (последовательность a предшествует последовательности b, если для некоторого s их начальные отрезки длины s равны, а (s+1) -ый член последовательности a меньше). Первой будет последовательность <1,1,...,1>, последней - последовательность <n,n,...,n>. Будем хранить последнюю напечатанную последовательность в массиве x[1]..x[k].

...x[1]...x[k] положить равными 1
...напечатать x
...last[1]...last[k] положить равным n
{напечатаны все до x включительно}
while x <> last do begin
| ...x := следующая за x последовательность
| ...напечатать x
end;

Опишем, как можно перейти от x к следующей последовательности. Согласно определению, у следующей последовательности первые s членов должны быть такими же, а (s+1) -ый - больше. Это возможно, если x[s+1] меньше n. Среди таких s нужно выбрать наибольшее (иначе полученная последовательность не будет непосредственно следующей). Соответствующее x[s+1] нужно увеличить на 1. Итак, надо, двигаясь с конца последовательности, найти самый правый член, меньший n (он найдется, т.к по предположению x<>last ), увеличить его на 1, а идущие за ним члены положить равными 1.

p:=k;
while not (x[p] < n) do begin
| p := p-1;
end;
{x[p] < n, x[p+1] =...= x[k] = n}
x[p] := x[p] + 1;
for i := p+1 to k do begin
| x[i]:=1;
end;

Замечание. Если членами последовательности считать числа не от 1 до n, а от 0 до n-1, то переход к следующему соответствует прибавлению единицы в n -ичной системе счисления.

2.1.2. В предложенном алгоритме используется сравнение двух массивов ( x <> last ). Устранить его, добавив булевскую переменную l и включив в инвариант соотношение$$$$ \text{ \texttt{l}~$\Leftrightarrow$ последовательность~\texttt{x}- последняя.% } \esquare $$ %\end{center} \end{problem}} \begin{problem*}$$

2.1.3. Напечатать все подмножества множества {1...k}.

Решение. Подмножества находятся во взаимно однозначном соответствии с последовательностями нулей и единиц длины k.

2.1.4. Напечатать все последовательности положительных целых чисел длины k, у которых i -ый член не превосходит i.

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

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

Решение. Перестановки будем хранить в массиве x[1]..x[n] и печатать в лексикографическом порядке. (Первой при этом будет перестановка $$\langle{1}\,{2}\ldots{n}\rangle $$, последней - $$\langle{n}\ldots{2}\,{1}\rangle$$. Для составления алгоритма перехода к следующей перестановке зададимся вопросом: в каком случае k -ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (т.е. членов с номерами больше k ). Мы должны найти наибольшее k, при котором это так, т.е. такое k, что$${x[k]} < {x[k+1]} > \ldots > {x[n]}$$ После этого значение x[k] нужно увеличить минимальным возможным способом, т.е. найти среди x[k+1]..x[n] наименьшее число, большее его. Поменяв x[k] с ним, остается расположить числа с номерами k+1..n так, чтобы перестановка была наименьшей, т.е. в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке.

Алгоритм перехода к следующей перестановке:

{<x[1]...x[n]> <> <n...2,1>}
k:=n-1;
{последовательность справа от k убывающая: x[k+1]>...>x[n]}
while x[k] > x[k+1] do begin
| k:=k-1;
end;
{x[k] < x[k+1] > ... >  x[n]}
t:=k+1;
{t <=n, все члены отрезка x[k+1] > ... > x[t] больше x[k]}
while (t < n) and (x[t+1] > x[k]) do begin
| t:=t+1;
end;
{x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]}
... обменять x[k] и x[t]
{x[k+1] > ... > x[n]}
... переставить участок x[k+1] ... x[n] в обратном порядке

Замечание. Программа имеет знакомый дефект: если t=n, то x[t+1] не определено.

2.3. Подмножества

2.3.1. Для заданных n и k ( $${k}\leq{n}$$ ) перечислить все k -элементные подмножества множества {1..n} }.

Решение. Будем представлять каждое подмножество последовательностью x[1]..x[n] нулей и единиц длины n, в которой ровно k единиц. (Другой способ представления разберем позже.) Такие последовательности упорядочим лексикографически (см. выше). Очевидный способ решения задачи - перебирать все последовательности как раньше, а затем отбирать среди них те, у которых k единиц - мы отбросим, считая его неэкономичным (число последовательностей с k единицами может быть много меньше числа всех последовательностей). Будем искать такой алгоритм, чтобы получение очередной последовательности требовало не более {C $$\cdot$$ n} действий.

В каком случае s -ый член последовательности можно увеличить, не меняя предыдущие? Если x[s] меняется с 0 на 1, то для сохранения общего числа единиц нужно справа от х[s] заменить 1 на 0. Для этого надо, чтобы справа от x[s] единицы были. Если мы хотим перейти к непосредственно} следующему, то x[s] должен быть первым справа} нулем, за которым стоят единицы. Легко видеть, что х[s+1]=1 (иначе х[s] не первый). Таким образом надо искать наибольшее За х[s+1] могут идти еще несколько единиц, а после них несколько нулей. Заменив х[s] на 1, надо выбрать идущие за ним члены так, чтобы последовательность была бы минимальна с точки зрения нашего порядка, т.е. чтобы сначала шли нули, а потом единицы. Вот что получается:

$$\begin{quote} первая последовательность: {0..01..1} ({n-k} нулей, {k} единиц); \end{quote}$$

$$\begin{quote} последняя последовательность: {1..10..0} ({k} единиц, {n-k} нулей); \end{quote}$$

$$\begin{quote} алгоритм перехода к следующей за {х[1]..x[n]} последовательности (предполагаем, что она есть): \end{quote}$$

s := n - 1;
while not ((x[s]=0) and (x[s+1]=1)) do begin
| s := s - 1;
end;
{s - член, подлежащий изменению с 0 на 1}
num:=0;
for k := s to n do begin
| num := num + x[k];
end;
{num - число единиц на участке x[s]...x[n], число нулей
 равно (длина - число единиц), т.е. (n-s+1) - num}
x[s]:=1;
for k := s+1 to n-num+1 do begin
| x[k] := 0;
end;
{осталось поместить num-1 единиц в конце}
for k := n-num+2 to n do begin
| x[k]:=1;
end;

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

2.3.2. Перечислить все возрастающие последовательности длины k из чисел 1..n в лексикографическом порядке. (Пример: при n=5, k=2 получаем: 12 13 14 15 23 24 25 34 35 45.)

Решение. Минимальной будет последовательность $$\langle{1}\,{2}\ldots{k}\rangle$$ ; максимальной - $$\langle{(n-k+1)}\ldots{(n-1)}\,{n}\rangle$$. В каком случае s -ый член последовательности можно увеличить? Ответ: если он меньше n-k+s. После увеличения s -го элемента все следующие должны возрастать с шагом 1. Получаем такой алгоритм перехода к следующему:

s:=n;
while not (x[s] < n-k+s) do begin
| s:=s-1;
end;
{s - номер элемента, подлежащего увеличению};
x[s] := x[s]+1;
for i := s+1 to n do begin
| x[i] := x[i-1]+1;
end;

2.3.3. Пусть мы решили представлять k -элементные подмножества множества {1..n} убывающими последовательностями длины k, упорядоченными по-прежнему лексикографически. (Пример: $$\texttt{21 31 32 41 42 43 51 52 53 54}$$.) Как выглядит тогда алгоритм перехода к следующей?

Ответ. Ищем наибольшее s, для которого х[s+1]+1 < x[s]. (Если такого s нет, полагаем s=0.) Увеличив x[s+1] на 1, кладем остальные минимально возможными ( x[t]=k+1-t для t>s ).

2.3.4. Решить две предыдущие задачи, заменив лексикографический порядок на обратный (раньше идут те, которые больше в лексикографическом порядке).

2.3.5. Перечислить все вложения (функции, переводящие разные элементы в разные) множества \{1..k} в {1..n} } (предполагается, что $${k}\le{n}$$ ). Порождение очередного элемента должно требовать не более $${C}\cdot{k}$$ действий.

Указание. Эта задача может быть сведена к перечислению подмножеств и перестановок элементов каждого подмножества.

2.4. Разбиения

2.4.1. Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4, разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)

Решение. Договоримся, что (1) в разбиениях слагаемые идут в невозрастающем порядке, (2) сами разбиения мы перечисляем в лексикографическом порядке. Разбиение храним в начале массива x[1]..x[n], при этом количество входящих в него чисел обозначим k. В начале x[1]=...=x[n]=1, k=n, в конце x[1]=n, k=1.

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

s := k - 1;
while not ((s=1) or (x[s-1] > x[s])) do begin
| s := s-1;
end;
{s - подлежащее увеличению слагаемое}
x [s] := x[s] + 1;
sum := 0;
for i := s+1 to k do begin
| sum := sum + x[i];
end;
{sum - сумма членов, стоявших после x[s]}
for i := 1 to sum-1 do begin
| x [s+i] := 1;
end;
k := s+sum-1;

2.4.2. Представляя по-прежнему разбиения как невозрастающие последовательности, перечислить их в порядке, обратном лексикографическому (для n=4, например, должно быть $$\texttt{4}$$, $$\texttt{3+1}$$, $$\texttt{2+2}$$, $$\texttt{2+1+1}$$, $$\texttt{1+1+1+1}$$ ).

Указание. Уменьшать можно первый справа член, не равный 1 ; найдя его, уменьшим на 1, а следующие возьмем максимально возможными (равными ему, пока хватает суммы, а последний - сколько останется).

2.4.3. Представляя разбиения как неубывающие последовательности, перечислить их в лексикографическом порядке. Пример для $${n=4}: \texttt{1+1+1+1}, \texttt{1+1+2}, \texttt{1+3}, \texttt{2+2}, \texttt{4}$$.

Указание. Последний член увеличить нельзя, а предпоследний - можно; если после увеличения на 1 предпоследнего члена за счет последнего нарушится возрастание, то из двух членов надо сделать один, если нет, то последний член надо разбить на слагаемые, равные предыдущему, и остаток, не меньший его.

2.4.4. Представляя разбиения как неубывающие последовательности, перечислить их в порядке, обратном лексикографическому. Пример для $${n=4}: \texttt{4, 2+2, 1+3, 1+1+2, 1+1+1+1}$$.

Указание. Чтобы элемент x[s] можно было уменьшить, необходимо, чтобы s=1 или x[s-1] < x[s]. Если x[s] не последний, то этого и достаточно. Если он последний, то нужно, чтобы $$\hbox{\texttt{x[s-1]}}\le\lfloor\hbox{\texttt{x[s]/2}}\rfloor$$ или s=1. (Здесь $$\lfloor\alpha\rfloor$$ обозначает целую часть $$\alpha$$.)

2.5. Коды Грея и аналогичные задачи

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

2.5.1. Перечислить все последовательности длины n из чисел 1..k в таком порядке, чтобы каждая следующая отличалась от предыдущей в единственной цифре, причем не более, чем на 1.

Решение. Рассмотрим прямоугольную доску ширины n и высоты k. На каждой вертикали будет стоять шашка. Таким образом, положения шашек соответствуют последовательностям из чисел 1..k длины n ( s -ый член последовательности соответствует высоте шашки на s -ой вертикали). На каждой шашке нарисуем стрелочку, которая может быть направлена вверх или вниз. Вначале все шашки поставим на нижнюю горизонталь стрелочкой вверх. Далее двигаем шашки по такому правилу: найдя самую правую шашку, которую можно подвинуть в направлении (нарисованной на ней) стрелки, двигаем ее на одну клетку в этом направлении, а все стоящие правее нее шашки (они уперлись в край) разворачиваем кругом.

Ясно, что на каждом шаге только одна шашка сдвигается, т.е. один член последовательности меняется на 1. Докажем индукцией по n, что проходятся все последовательности из чисел 1..k. Случай n=1 очевиден. Пусть n>1. Все ходы поделим на те, где двигается последняя шашка, и те, где двигается не последняя. Во втором случае последняя шашка стоит у стены, и мы ее поворачиваем, так что за каждым ходом второго типа следует k-1 ходов первого типа, за время которых последняя шашка побывает во всех клетках. Если мы теперь забудем о последней шашке, то движения первых n-1 по предположению индукции пробегают все последовательности длины n-1 по одному разу; движения же последней шашки из каждой последовательности длины n-1 делают k последовательностей длины n.

В программе, помимо последовательности x[1]..x[n], будем хранить массив d[1]..d[n] из чисел +1 и -1 ( +1 соответствует стрелке вверх, -1 - стрелке вниз).

Начальное состояние: x[1]=...=x[n]=1 ; d[1]=...=d[n]=1.

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

{если можно, сделать шаг и положить p := true, если нет,
 положить p := false }
i := n;
while (i > 1) and
| (((d[i]=1) and (x[i]=n)) or ((d[i]=-1) and (x[i]=1)))
|   do begin
| i:=i-1;
end;
if (d[i]=1 and x[i]=n) or (d[i]=-1 and x[i]=1) then begin
| p:=false;
end else begin
| p:=true;
| x[i] := x[i] + d[i];
| for j := i+1 to n do begin
| | d[j] := - d[j];
| end;
end;

Замечание. Для последовательностей нулей и единиц возможно другое решение, использующее двоичную систему. (Именно оно связывается обычно с названием "коды Грея".)

Запишем подряд все числа от $$0$$ до $$2^n-1$$ в двоичной системе. Например, для $$n=3$$ напишем:$$000\quad 001\quad 010\quad 011 \quad 100\quad 101\quad 110\quad 111$$ Затем каждое из чисел подвергнем преобразованию, заменив каждую цифру, кроме первой, на ее сумму с предыдущей цифрой (по модулю $$2$$ ). Иными словами, число $$a_1, a_2,\ldots,a_n$$ преобразуем в $$a_1, a_1 + a_2, a_2 + a_3,\ldots,a_{n-1} + a_n$$ (сумма по модулю $$2$$ ). Для $$n=3$$ получим:$$000\quad 001\quad 011\quad 010\quad 110 \quad 111\quad 101\quad 100$$

Легко проверить, что описанное преобразование чисел обратимо (и тем самым дает все последовательности по одному разу). Кроме того, двоичные записи соседних чисел отличаются заменой конца $$011\ldots1$$ на конец $$100\ldots0$$, что - после преобразования - приводит к изменению единственной цифры.

Применение кода Грея. Пусть есть вращающаяся ось, и мы хотим поставить датчик угла поворота этой оси. Насадим на ось барабан, выкрасим половину барабана в черный цвет, половину в белый и установим фотоэлемент. На его выходе будет в половине случаев $$0$$, а в половине $$1$$ (т.е. мы измеряем угол "с точностью до $$180$$ ").

Развертка барабана:

Сделав рядом другую дорожку из двух черных и белых частей и поставив второй фотоэлемент, получаем возможность измерить угол с точностью до $$90^\circ$$:

Сделав третью,

мы измерим угол с точностью до $$45^\circ$$ и т.д. Эта идея имеет, однако, недостаток: в момент пересечения границ сразу несколько фотоэлементов меняют сигнал, и если эти изменения произойдут не совсем одновременно, на какое-то время показания фотоэлементов будут бессмысленными. Коды Грея позволяют избежать этой опасности. Сделаем так, чтобы на каждом шаге менялось показание лишь одного фотоэлемента (в том числе и на последнем, после целого оборота).

Написанная нами формула позволяет легко преобразовать данные от фотоэлементов в двоичный код угла поворота.

Заметим также, что геометрически существование кода Грея означает наличие "гамильтонова цикла" в $$n$$ -мерном кубе (возможность обойти все вершины куба по разу, двигаясь по ребрам, и вернуться в исходную вершину).

2.5.2. Напечатать все перестановки чисел 1..n так, чтобы каждая следующая получалась из предыдущей перестановкой (транспозицией) двух соседних чисел. Например, при n=3 допустим такой порядок:$$\begin{center}\ttfamily 3.2 1~$\to$ 2 3.1~$\to$ 2.1 3~$\to$ 1 2.3~$\to$ 1.3 2~$\to$ 3 1 2 \end{center}$$ (между переставляемыми числами вставлены точки).

Решение. Наряду с множеством перестановок рассмотрим множество последовательностей y[1]..y[n] целых неотрицательных чисел, для которых $$\hbox{\texttt{y[1]}}\le \hbox{\texttt{0}}$$, $$\dots$$, $$\hbox{\texttt{y[n]}}\le \hbox{\texttt{n-1}}$$. В нем столько же элементов, сколько в множестве всех перестановок, и мы сейчас установим между ними взаимно однозначное соответствие. Именно, каждой перестановке поставим в соответствие последовательность y[1]..y[n], где y[i] - количество чисел, меньших i и стоящих левее i в этой перестановке. Взаимная однозначность вытекает из такого замечания. Перестановка чисел 1..n получается из перестановки чисел 1..n-1 добавлением числа n, которое можно вставить на любое из n мест. При этом к сопоставляемой с ней последовательности добавляется еще один член, принимающий значения от 0 до n-1, а предыдущие члены не меняются. При этом оказывается, что изменение на единицу одного из членов последовательности y соответствует транспозиции двух соседних чисел, если все следующие числа последовательности y принимают максимально или минимально возможные для них значения. Именно, увеличение y[i] на 1 соответствует транспозиции числа i с его правым соседом, а уменьшение - с левым.

Теперь вспомним решение задачи о перечислении всех последовательностей, на каждом шаге которого один член меняется на единицу. Заменив прямоугольную доску доской в форме лестницы (высота i -ой вертикали равна i ) и двигая шашки по тем же правилам, мы перечислим все последовательности y, причем i -ый член будет меняться как раз только если все следующие шашки стоят у края. Надо еще уметь параллельно с изменением y корректировать перестановку. Очевидный способ требует отыскания в ней числа i ; это можно облегчить, если помимо самой перестановки хранить функцию$$\\begin{center} \texttt{i}~$\mapsto$ позиция числа~\texttt{i} в~перестановке, \end{center}$$ т.е. обратное к перестановке отображение, и соответствующим образом ее корректировать. Вот какая получается программа:

program test;
| const n=...;
| var
|   x: array [1..n] of 1..n; {перестановка}
|   inv_x: array [1..n] of 1..n; {обратная перестановка}
|   y: array [1..n] of integer; {y[i] < i}
|   d: array [1..n] of -1..1; {направления}
|   b: boolean;
|
| procedure print_x;
| | var i: integer;
| begin
| | for i:=1 to n do begin
| | | write (x[i], ' ');
| | end;
| | writeln;
| end;
|
| procedure set_first;{первая: y[i]=0 при всех i}
| | var i : integer;
| begin
| | for i := 1 to n do begin
| | | x[i] := n + 1 - i;
| | | inv_x[i] := n + 1 - i;
| | | y[i]:=0;
| | | d[i]:=1;
| | end;
| end;
|
| procedure move (var done : boolean);
| | var i, j, pos1, pos2, val1, val2, tmp : integer;
| begin
| | i := n;
| | while (i > 1) and (((d[i]=1) and (y[i]=i-1)) or
| | |  ((d[i]=-1) and (y[i]=0))) do begin
| | | i := i-1;
| | end;
| | done := (i>1); {упрощение: первый член нельзя менять}
| | if done then begin
| | | y[i] := y[i]+d[i];
| | | for j := i+1 to n do begin
| | | | d[j] := -d[j];
| | | end;
| | | pos1 := inv_x[i];
| | | val1 := i;
| | | pos2 := pos1 + d[i];
| | | val2 := x[pos2];
| | | {pos1, pos2 - номера переставляемых элементов;
| | |   val1, val2 - их значения; val2 < val1}
| | | tmp := x[pos1];
| | | x[pos1] := x[pos2];
| | | x[pos2] := tmp;
| | | tmp := inv_x[val1];
| | | inv_x[val1] := inv_x[val2];
| | | inv_x[val2] := tmp;
| | end;
| end;
|
begin
| set_first;
| print_x;
| b := true;
| {напечатаны все перестановки до текущей включительно;
|   если b ложно, то текущая - последняя}
| while b do begin
| | move (b);
| | if b then print_x;
| end;
end.

2.6. Несколько замечаний

Посмотрим еще раз на использованные нами приемы. Вначале удавалось решить задачу по такой схеме: определяем порядок на подлежащих перечислению объектах и явно описываем процедуру перехода от данного объекта к следующему (в смысле этого порядка). В задаче о кодах Грея потребовалось хранить, помимо текущего объекта, и некоторую дополнительную информацию (направления стрелок). Наконец, в задаче о перечислении перестановок (на каждом шаге допустима одна транспозиция) мы применили такой прием: установили взаимно однозначное соответствие между перечисляемым множеством и другим, более просто устроенным. Таких соответствий в комбинаторике известно много. Мы приведем несколько задач, связанных с так называемыми " числами Каталана ".

2.6.1. Перечислить все последовательности длины 2n, составленные из n единиц и n минус единиц, у которых сумма любого начального отрезка неотрицательна, т.е. число минус единиц в нем не превосходит числа единиц. (Число таких последовательностей называют числом Каталана ; формулу для чисел Каталана см. в следующем разделе.)

Решение. Изображая единицу вектором (1,1), а минус единицу вектором (1,-1), можно сказать, что мы ищем пути из точки (0,0) в точку (n,0), не опускающиеся ниже оси абсцисс.

Будем перечислять последовательности в лексикографическом порядке, считая, что -1 предшествует 1. Первой последовательностью будет "пила"$$\begin{center}\ttfamily 1, -1, 1, -1, \dots \end{center}$$ а последней - "горка"$$\begin{center}\ttfamily 1, 1, 1,\dots, 1, -1, -1,\dots, -1. \end{center}$$

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

...
type array2n = array [1..2n] of integer;
...
procedure get_next (var a: array2n; var last: Boolean);
| {в a помещается следующая последовательность, если}
| {она есть (при этом last:=false), иначе last:=true}
| var k, i, sum: integer;
begin
| k:=2*n;
| {инвариант: в a[k+1..2n] только минус единицы}
| while a[k] = -1 do begin k:=k-1; end;
| {k - максимальное среди тех, для которых a[k]=1}
| while (k>0) and (a[k] = 1) do begin k:=k-1; end;
| {a[k] - самая правая -1, за которой есть 1;
|  если таких нет, то k=0}
| if k = 0 then begin
| | last := true;
| end else begin
| | last := false;
| | i:=0; sum:=0;
| | {sum = a[1]+...+a[i]}
| | while i< >k do begin
| | | i:=i+1; sum:= sum+a[i];
| | end;
| | {sum = a[1]+...+a[k], a[k]=-1}
| |  a[k]:= 1; sum:= sum+2;
| | {вплоть до a[k] все изменено, sum=a[1]+...+a[k]}
| | while k < > 2*n do begin
| | | k:=k+1;
| | | if sum > 0 then begin
| | | | a[k]:=-1
| | | end else begin
| | | | a[k]:=1;
| | | end;
| | | sum:= sum+a[k];
| | end;
| | {k=2n, sum=a[1]+...a[2n]=0}
| end;
end;

2.6.2. Перечислить все расстановки скобок в произведении n сомножителей. Порядок сомножителей не меняется, скобки полностью определяют порядок действий. Например, для n=4 есть 5 расстановок:$$\begin{center}\ttfamily ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)). \end{center}$$

Указание. Каждому порядку действий соответствует последовательность команд стекового калькулятора, описанного в пункте 8.3.

2.6.3. На окружности задано 2n точек, пронумерованных от 1 до 2n. Перечислить все способы провести n непересекающихся хорд с вершинами в этих точках.

2.6.4. Перечислить все способы разрезать n -угольник на треугольники, проведя n-2 его диагонали.

(Мы вернемся к разрезанию многоугольника в разделе о динамическом программировании, пункт 8.1.)

Еще один класс задач на перечисление всех элементов заданного множества мы рассмотрим ниже, обсуждая метод поиска с возвратами (backtracking).

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

Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: $$C_n^k$$ - число всех $$k$$ -элементных подмножеств $$n$$ -элементного множества - можно найти, заполняя таблицу по формулам$$\begin{alignat*}{2} C_n^0 =C_n^n = 1\qquad (n \ge 1)\\ C_n^k =C_{n-1}^{k-1} + C_{n-1}^k\qquad (n > 1, 0 < k n) \end{alignat*}$$ или по формуле$$C_n^k=\frac{n!}{k!\cdot (n-k)!}.$$ (Первый способ эффективнее, если надо вычислить много значений $$C_n^k$$.)

Приведем другие примеры.

2.7.1. (Число разбиений; предлагалась на Всесоюзной олимпиаде по программированию 1988 года) Пусть $$P(n)$$ - число разбиений целого положительного $$n$$ на целые положительные слагаемые (без учета порядка, $$1+2$$ и $$2+1$$ - одно и то же разбиение). При $$n=0$$ положим $$P(n) = 1$$ (единственное разбиение не содержит слагаемых). Построить алгоритм вычисления $$P(n)$$ для заданного $$n$$.

Решение. Можно доказать (это нетривиально) такую формулу для $$P(n)$$:$$P(n) = P(n-1)+P(n-2)-P(n-5)-P(n-7)+P(n-12)+P(n-15) +\ldots$$ (знаки у пар членов чередуются, вычитаемые в одной паре равны $$(3q^2-q)/2$$ и $$(3q^2+q)/2$$ ; сумма конечна - мы считаем, что $$P(k)=0$$ при $$k<0$$ ).

Однако и без ее использования можно придумать способ вычисления $$P(n)$$, который существенно эффективнее перебора и подсчета всех разбиений.

Обозначим через $$R(n,k)$$ (для $$n\ge 0$$, $$k\ge0$$ ) число разбиений $$n$$ на целые положительные слагаемые, не превосходящие $$k$$. (При этом $$R(0,k)$$ считаем равным $$1$$ для всех $$k\ge 0$$.) Очевидно, $$P(n)=R(n,n)$$. Все разбиения $$n$$ на слагаемые, не превосходящие $$k$$, разобьем на группы в зависимости от максимального слагаемого (обозначим его $$i$$ ). Число $$R(n,k)$$ равно сумме (по всем $$i$$ от $$1$$ до $$k$$ ) количеств разбиений со слагаемыми не больше $$k$$ и максимальным слагаемым, равным $$i$$. А разбиения $$n$$ на слагаемые не более $$k$$ с первым слагаемым, равным $$i$$, по существу представляют собой разбиения $$n-i$$ на слагаемые, не превосходящие $$i$$ (при $$i\le k$$ ). Так что$$\begin{alignat*}{2} R(n,k)=\sum\limits_{i=1}^{k} R (n-i,i)\qquad \text{при $k\le n$},\\ R(n,k)=R (n,n)\qquad \text{при $k \ge n$}, \end{alignat*}$$ что позволяет заполнять таблицу значений функции $$R$$.

2.7.2. (Счастливые билеты; предлагалась на Всесоюзной олимпиаде по программированию 1989 года.) Последовательность из $$2n$$ цифр (каждая цифра от $$0$$ до $$9$$ ) называется счастливым билетом, если сумма первых $$n$$ цифр равна сумме последних $$n$$ цифр. Найти число счастливых последовательностей данной длины.

Решение. (Сообщено одним из участников олимпиады; к сожалению, не могу указать фамилию, так как работы проверялись зашифрованными.) Рассмотрим более общую задачу: найти число последовательностей, где разница между суммой первых $$n$$ цифр и суммой последних $$n$$ цифр равна $$k$$ ( $$k = -9n,\ldots, 9n$$ ). Пусть $$T(n,k)$$ - число таких последовательностей.

Разобьем множество таких последовательностей на классы в зависимости от разницы между первой и последней цифрами. Если эта разница равна $$t$$, то разница между суммами групп из оставшихся $$n-1$$ цифр равна $$k-t$$. Учитывая, что пар цифр с разностью $$t$$ бывает $$10 - |t|$$, получаем формулу$$T(n,k) = \sum\limits_{t=-9}^{9} (10-|t|) T(n-1,k-t).$$ (Некоторые слагаемые могут отсутствовать, так как $$k-t$$ может быть слишком велико.)

В некоторых случаях ответ удается получить в виде явной формулы.

2.7.3. Доказать, что число Каталана (количество последовательностей длины $$2n$$ из $$n$$ единиц и $$n$$ минус единиц, в любом начальном отрезке которых не меньше единиц, чем минус единиц) равно $$C_{2n}^n/(n+1)$$.

Указание. Число Каталана есть число ломаных, идущих из $$(0,0)$$ в $$(2n,0)$$ шагами $$(1,1)$$ и $$(1,-1)$$, не опускающихся в нижнюю полуплоскость, т.е. разность числа всех ломаных (которое есть $$C_{2n}^{n}$$ ) и числа ломаных, опускающихся в нижнюю полуплоскость. Последние можно описать также как ломаные, пересекающие прямую $$y=-1$$. Отразив их кусок справа от самой правой точки пересечения относительно указанной прямой, мы установим взаимно однозначное соответствие между ними и ломаными из $$(0,0)$$ в $$(2n,-2)$$. Остается проверить, что $$C_{2n}^{n}-C_{2n}^{n+1}=C_{2n}^{n}/(n+1)$$.