можными (равными ему, пока хватает суммы, а последний - сколько
останется).
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, ...
