В данной статье будут рассмотрены следующие вопросы:
- Двоичные коды Грея. Их существование. Перебор подмножеств данного множества в порядке минимального изменения.
- Существование и реализация перебора подмножеств из k элементов в порядке минимального изменения.
Итак, приступим.
Двоичный код Грея
Двоичным кодом Грея порядка n называется последовательность n-битных кодов, в которой любые два соседних кода различаются ровно в одном разряде.
Пример кодов Грея порядка 2:
- 00
- 01
- 11
- 10
Нетрудно заметить, что такая последовательность не единственная(её как минимум можно обратить). Поэтому давайте разберемся в существовании двоичных кодов Грея других порядков и заодно выделим какой-то один вид таких последовательностей для дальнейшей работы.
Существование
Существование кодов Грея легко доказывается по индукции.
База — — пустая последовательность.
Переход. Пусть — последовательность кодов Грея порядка
.
— последовательность
записанная в обратном порядке. Тогда последовательность
получается приписыванием нуля слева к каждому коду в последовательности
и единицы слева к каждому коду
и последующим их объединением, т.е.
. Нетрудно проверить, что свойство кодов Грея в последовательности
, построенную таким образом, не нарушается.
Коды Грея, полученные таким способом, называются рефлексивными или симметрично отраженными. В дальнейшем мы будем рассматривать именно такие рефлексивные двоичные коды Грея.
Перебор подмножеств данного множества в порядке минимального изменения
Рассмотрим следующую задачу: «Дано множество из n элементов. Требуется вывести все его подмножества в таком порядке, что каждое следующее подмножество получается из предыдущего удалением или добавлением ровно одного элемента(т.е. в порядке минимального изменения).»
Будем считать, что элементы нашего множества пронумерованы от 1 до n. Тогда любому набору элементов множества можно поставить в соответствие n-битный двоичный код: если i-ый элемент множества входит в набор, то i-ый бит кода равен единице, иначе нулю. Таким образом, перебор всех подмножеств сводится к перебору двоичных кодов, а перебор подмножеств в порядке минимального изменения — к перебору двоичных кодов Грея.
Идея алгоритма рекурсивного перебора кодов Грея непременно следует из доказательства их существования.
Собственно, как и говорилось в доказательстве, код Грея порядка n получается из кода Грея порядка n-1 приписыванием нуля слева(этому соответствует вызов функции
и присвоение перед ним) и обратного кода Грея порядка n-1 приписыванием единицы слева(этому соответствует вызов функции
и присвоение перед ним).
Перейдем к оценке сложности данного алгоритма. Очевидно, что дерево вызовов функции является полным двоичным деревом высоты n. Следовательно, общее число вызовов функции при генерации кодов Грея порядка n есть ни что иное, как
, что равно количеству всевозможных n-битных кодов. Следовательно, алгоритм оптимален.
В качестве упражнения читателю предлагается проанализировать следующий, более короткий, алгоритм рекурсивного перебора.

Также хотелось бы сказать о существовании итеративного алгоритма перебора и других полезных свойствах кодов Грея, которые не рассматриваются в данной статье, и о которых можно узнать из других источников, например Википедии.
А теперь давайте перейдем к последней и самой интересной задаче.
Перебор подмножеств из k элементов в порядке минимального изменения.
Начнем с постановки задачи: «Дано множество из n элементов. Требуется вывести все его подмножества, состоящие ровно из k элементов, в таком порядке, что каждое следующее подмножество получается из предыдущего заменой ровно одного элемента(т.е. в порядке минимального изменения).»
Здесь сразу приходит в голову идея алгоритма из предыдущей задачи с дополнительной проверкой числа единиц при выводе. Но при этом возникает вопрос о корректности этого алгоритма(нам никто не гарантирует расположение кодов с k единицами в последовательности в порядке минимального изменения — с разницей в двух разрядах). Поэтому мы не станем останавливаться на этом и проведем поиски алгоритма с асимптотикой, лучшей, чем
и попытаемся доказать его корректность.
Введем некоторые обозначения:
— строка, получаемая конкатенацией символа x (m раз) и конкатенацией символа y (k раз). Пример:
.
— последовательность всех n-битных кодов с k единицами, в которой коды идут в том порядке, в котором они расположены в последовательности
.
— последовательность всех n-битных кодов с k единицами, в которой коды идут в том порядке, в котором они расположены в последовательности
.
Лемма
Первый двоичный код с единицами в последовательности
имеет вид
, а последний —
или
, если
.
Доказательство
Доказывать будем индукцией по и
.
База — — верно(нетрудно проверить приведенные формулы для двух кодов 0 и 1).
Переход. Пусть формулы верны для и любого
. Вспомним формулу из доказательства существования кодов Грея:
. Отсюда получим, что первый код с
единицами в последовательности
с приписанным слева нулем является первым кодом с
единицами в последовательности
. При
получим единственный код с
единицей, для которого формула также верна. При
последний код с
единицами в последовательности
есть первый код с
единицей и приписанной слева единицей в последовательности
. При
формула также верна.
Теорема
Соседние двоичные коды в последовательности различаются ровно в двух разрядах.
Доказательство
Доказывать будем также индукцией по и
.
База — — очевидно(всего один возможный код в последовательности).
Переход. Пусть теорема верна для и
. При
или
имеем всего один код в последовательности
. При
соседние слова находящиеся полностью в
или в
по индукционному предположению различаются ровно в двух разрядах. Остается проверить одну пару соседних кодов в
последний код с
единицами в
и первый код с
единицами в
(последний с
единицей в
с приписанной слева единицей). По лемме, при
, они имеют вид
и
соответственно, а при
—
и
. Нетрудно видеть, что они различаются ровно в двух разрядах.
Теперь мы можем сформулировать замечательные следствия из теоремы.
- Наивный алгоритм, предложенный ранее, корректен.
- Последовательность
задается следующим рекуррентным соотношением:
.
- Последовательность
задается следующим рекуррентным соотношением:
.
Эти следствия можно и нужно использовать для написания программы рекурсивного перебора подмножеств из k элементов в порядке минимального изменения.
Хотелось бы обратить внимание на то, что вывод двоичного кода подразумевает еще и заполнение оставшихся разрядов единицами или нулями, в зависимости от значения u и v.
Перейдем к оценке сложности приведенного алгоритма. Заметим, что при углублении в рекурсию значение u всегда уменьшается. То есть мы сделаем не больше n углублений для достижения какого-то двоичного кода. Всего таких кодов — . Получаем итоговую асимптотику
. Это довольно грубая оценка, но она всяко лучше
, особенно при величине k стремящейся к n: алгоритм практически линеен.
Легко заметить, что дерево вызовов будет двоичным, но не будет полным. Проведем параллель оценки сложности в терминах деревьев: каждый лист соответствует получению какого-то двоичного кода, а расстояние до листа в дереве не превышает n. Оценка
говорит нам о том, что мы просто просуммировали верхнюю оценку длин — n — всех путей до листов. Но ведь многие из этих путей имеют длину меньше n, а еще больше путей пересекаются друг с другом. Это должно наталкивать нас на мысль, что асимптотика приведенного алгоритма на самом деле намного лучше.
Точная оценка асимптотики — далеко не тривиальный факт, который можно найти в книге Э.Рейнгольда, Ю.Нивергельта и Н.Део «Комбинаторные алгоритмы. Теория и практика», либо попытаться доказать самому.
На этом хотелось бы закончить статью. Спасибо за внимание и до скорых встреч.
Автор: demolishka