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