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