ется последняя шашка, и те, где двигается не последняя. Во вто-
ром случае последняя шашка стоит у стены, и мы ее поворачиваем,
так что за каждым ходом второго типа следует 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 непересекающихся хорд
