Материал: 00464

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

Для заданных n и k ( ) перечислить все k -элементные подмножества множества {1..n} }.

Решение. Будем представлять каждое подмножество последовательностью x[1]..x[n] нулей и единиц длины n, в которой ровно k единиц. (Другой способ представления разберем позже.) Такие последовательности упорядочим лексикографически (см. выше). Очевидный способ решения задачи - перебирать все последовательности как раньше, а затем отбирать среди них те, у которых k единиц - мы отбросим, считая его неэкономичным (число последовательностей с k единицами может быть много меньше числа всех последовательностей). Будем искать такой алгоритм, чтобы получение очередной последовательности требовало не более {C n} действий.

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

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

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;

{осталось поместить num-1 единиц в конце}

for k := n-num+2 to n do begin

| x[k]:=1;

end;

Другой способ представления подмножеств - это перечисление их элементов. Чтобы каждое подмножество имело ровно одно представление, договоримся перечислять элементы в возрастающем порядке. Приходим к такой задаче.

Перечислить все возрастающие последовательности длины k из чисел 1..n в лексикографическом порядке. (Пример: при n=5, k=2 получаем: 12 13 14 15 23 24 25 34 35 45.)

Решение. Минимальной будет последовательность ; максимальной - . В каком случае 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;

Пусть мы решили представлять k -элементные подмножества множества {1..n} убывающими последовательностями длины k, упорядоченными по-прежнему лексикографически. (Пример: .) Как выглядит тогда алгоритм перехода к следующей?

Ответ. Ищем наибольшее s, для которого х[s+1]+1 < x[s]. (Если такого s нет, полагаем s=0.) Увеличив x[s+1] на 1, кладем остальные минимально возможными ( x[t]=k+1-t для t>s ).

Решить две предыдущие задачи, заменив лексикографический порядок на обратный (раньше идут те, которые больше в лексикографическом порядке).

Перечислить все вложения (функции, переводящие разные элементы в разные) множества \{1..k} в {1..n} } (предполагается, что ). Порождение очередного элемента должно требовать не более действий.

Указание. Эта задача может быть сведена к перечислению подмножеств и перестановок элементов каждого подмножества.

Разбиения

Перечислить все разбиения целого положительного числа 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;

Представляя по-прежнему разбиения как невозрастающие последовательности, перечислить их в порядке, обратном лексикографическому (для n=4, например, должно быть , , , , ).

Указание. Уменьшать можно первый справа член, не равный 1 ; найдя его, уменьшим на 1, а следующие возьмем максимально возможными (равными ему, пока хватает суммы, а последний - сколько останется).

Представляя разбиения как неубывающие последовательности, перечислить их в лексикографическом порядке. Пример для .

Указание. Последний член увеличить нельзя, а предпоследний - можно; если после увеличения на 1 предпоследнего члена за счет последнего нарушится возрастание, то из двух членов надо сделать один, если нет, то последний член надо разбить на слагаемые, равные предыдущему, и остаток, не меньший его.

Представляя разбиения как неубывающие последовательности, перечислить их в порядке, обратном лексикографическому. Пример для .

Указание. Чтобы элемент x[s] можно было уменьшить, необходимо, чтобы s=1 или x[s-1] < x[s]. Если x[s] не последний, то этого и достаточно. Если он последний, то нужно, чтобы или s=1. (Здесь обозначает целую часть .)

Лекция 5. Коды Грея. Коды Грея и аналогичные задачи

Иногда бывает полезно перечислять объекты в таком порядке, чтобы каждый следующий минимально отличался от предыдущего. Рассмотрим несколько задач такого рода.

Перечислить все последовательности длины 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

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

Замечание. Для последовательностей нулей и единиц возможно другое решение, использующее двоичную систему. (Именно оно связывается обычно с названием "коды Грея".)

Запишем подряд все числа от до в двоичной системе. Например, для напишем:

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

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

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

Развертка барабана:

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

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

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

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

Заметим также, что геометрически существование кода Грея означает наличие "гамильтонова цикла" в -мерном кубе (возможность обойти все вершины куба по разу, двигаясь по ребрам, и вернуться в исходную вершину).