Коды Грея и задачи перебора

В данной статье будут рассмотрены следующие вопросы:

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

Точная оценка асимптотики — далеко не тривиальный факт, который можно найти в книге Э.Рейнгольда, Ю.Нивергельта и Н.Део «Комбинаторные алгоритмы. Теория и практика», либо попытаться доказать самому.

На этом хотелось бы закончить статью. Спасибо за внимание и до скорых встреч.