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