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

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

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

     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
        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, то переход к следующему соответствует
прибавлению 1 в n-ичной системе счисления.

     2.1.2. В предложенном алгоритме используется сравнение двух
массивов x <> last. Устранить его, добавив булевскую  переменную
l и включив в инвариант соотношение l <=> последовательность x -
последняя.

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

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

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


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

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

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

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

  {<x[1],...,x[n-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.2.2. Модифицировать алгоритм перехода к следующей  перес-
тановке так, чтобы он сам проверял, не является ли данная перес-
тановка последней.

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

     2.3.1. Перечислить все k-элементные подмножества  множества
{1..n}.

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

                  ______________________
               x |________|0|1...1|0...0|
                           s

За х[s+1] могут идти еще несколько единиц, а после них несколько
нулей. Заменив х[s] на 1, надо выбрать идущие за ним члены  так,
чтобы последовательность была бы минимальна с точки зрения наше-
го  порядка,  т. е. чтобы сначала шли нули, а потом единицы. Вот
что получается:

  первая последовательность    0...01...1 (n-k нулей, k единиц)
  последняя последовательность 1...10...0 (k единиц, n-k нулей)

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

        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;
        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.)

     Решение. Минимальной будет последовательность 1, 2, ..., k;
максимальной - (n-k+1),..., (n-1), n. В каком случае  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,
упорядоченными по-прежнему лексикографически. (Пример : 21 31 32
41 42 43 51 52 53 54.) Как выглядит тогда  алгоритм  перехода  к
следующей?

     Ответ. Ищем наибольшее s, для которого х[s]-x[s+1]>1. (Если
такого 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 <= n). Порождение очередного элемента должно требовать
порядка 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, например, должно получиться 4,  3+1,  2+2,
2+1+1, 1+1+1+1).
     Указание. Уменьшать можно первый справа член, не равный  1;
найдя  его,  уменьшим на 1, а следующие возьмем максимально воз-
можными  (равными ему, пока хватает суммы, а последний - сколько
останется).

     2.4.3. Представляя  разбиения  как  неубывающие  последова-
тельности,  перечислить  их в лексикографическом порядке. Пример
для n=4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4;
     Указание. Последний член увеличить нельзя, а  предпоследний
- можно; если после увеличения на 1 предпоследнего члена за счет
последнего нарушится возрастание, то из двух членов надо сделать
один,  если  нет,  то  последний член надо разбить на слагаемые,
равные предыдущему, и остаток, не меньший его.

     2.4.4.  Представляя  разбиения  как  неубывающие последова-
тельности, перечислить их в порядке, обратном лексикографическо-
му. Пример для n=4: 4, 2+2, 1+3, 1+1+2, 1+1+1+1.
     Указание.  Чтобы элемент x[s] можно было уменьшить, необхо-
димо, чтобы s = 1 или x[s-1] < x[s]. Если x[s] не последний,  то
этого и достаточно. Если он последний, то нужно, чтобы x[s-1] <=
(целая часть (x[s]/2)) или s=1.


     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 {i=1}
  | 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 001 010 011 100 101 110 111

Затем  каждое из чисел подвергнем преобразованию, заменив каждую
цифру, кроме первой, на ее сумму с предыдущей цифрой (по  модулю
2). Иными словами, число

     a[1], a[2],...,a[n]  преобразуем в
     a[1], a[1] + a[2], a[2] + a[3],...,a[n-1] + a[n]

(сумма по модулю 2). Для n=3 получим:

            000 001 011 010  110  111 101 100.

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

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

     Развертка барабана:
                     0       1
             -> |_|_|_|_|*|*|*|*| <- (склеить бока).

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

                   0   0   1   1
                   0   1   0   1
                 _ _ _ _
                |_|_|_|_|*|*|*|*|
                |_|_|*|*|_|_|*|*|

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

                 0 0 0 0 1 1 1 1
                 0 0 1 1 0 0 1 1
                 0 1 0 1 0 1 0 1
                 _ _ _ _
                |_|_|_|_|*|*|*|*|
                |_|_|*|*|_|_|*|*|
                |_|*|_|*|_|*|_|*|

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

                 0 0 0 0 1 1 1 1
                 0 0 1 1 1 1 0 0
                 0 1 1 0 0 1 1 0
                 _ _ _ _
                |_|_|_|_|*|*|*|*|
                |_|_|*|*|*|*|_|_|
                |_|*|*|_|_|*|*|_|

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

     2.5.2. Напечатать все перестановки чисел  1..n  так,  чтобы
каждая   следующая   получалась   из   предыдущей  перестановкой
(транспозицией) двух соседних чисел. Например, при n = 3  допус-
тим такой порядок: 3.2 1 -> 2 3.1 -> 2.1 3 -> 1 2.3 -> 1.3 2  ->
3 1 2 (между переставляемыми числами вставлены точки).

     Решение. Наряду с множеством перестановок  рассмотрим  мно-
жество  последовательностей y[1]..y[n] целых неотрицательных чи-
сел, у которых y[1] <= 0,..., y[n] <= 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; это можно об-
легчить, если помимо самой перестановки хранить функцию i  |--->
позиция  числа i в перестановке (обратное к перестановке отобра-
жение), и соответствующим образом ее корректировать.  Вот  какая
получается программа:

 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
 | | |          ((y[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 - их значения}
 | | | 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.  Первой  последова-
тельностью будет "пила"
        1, -1, 1, -1, ...
а последней - "горка"
        1, 1, 1, ..., 1, -1, -1, ..., -1.
     Как перейти от последовательности к следующей? До некоторо-
го места они должны совпадать, а затем надо заменить  -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; 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=n, sum=a[1]+...a[2n]=0}
    | end;
    end;

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

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

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

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

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

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

     Иногда  можно  найти  количество  объектов  с  тем или иным
свойством, не перечисляя их. Классический пример: 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).)

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

     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) +...

(знаки у пар членов чередуются, вычитаемые в  одной  паре  равны
(3*q*q-q)/2 и (3*q*q+q)/2).
     Однако и без ее использования можно придумать способ вычис-
ления  P(n), который существенно эффективнее перебора и подсчета
всех разбиений.
     Обозначим через R(n,k) (при n >= 0, k >= 0) число разбиений
n  на  целые  положительные  слагаемые, не превосходящие k. (При
этом  R(0,k) считаем равным 1 для всех k >= 0.) Очевидно, P(n) =
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) = сумма по i от 1 до k чисел R(n-i,i) при k <= n;
    R(n,k) = R(n,n) при k >= n,

что позволяет заполнять таблицу значений функции R.

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

     Решение. (Сообщено одним из участников олимпиады; к сожале-
нию,  не могу указать фамилию, так как работы проверялись зашиф-
рованными.) Рассмотрим более общую задачу: найти число  последо-
вательностей,  где  разница  между суммой первых n цифр и суммой
последних n цифр равна k (k = -9n,..., 9n). Пусть T(n, k) - чис-
ло таких последовательностей.
     Разобьем  множество  таких  последовательностей на классы в
зависимости от разницы между первой и  последней  цифрами.  Если
эта разница равна t, то разница между суммами групп из оставших-
ся  n-1 цифр равна k-t. Учитывая, что пар цифр с разностью t бы-
вает 10 - (модуль t), получаем формулу
   T(n,k) = сумма по t от -9 до 9 чисел (10-|t|) * T(n-1,  k-t).
(Некоторые слагаемые могут отсутствовать, так как k-t может быть
слишком велико.)