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

Пусть имеется множество A={a₁, a₂, …, a_n}. Имеется 2n подмножеств этого множества. Действительно, каждый из элементов независимо от других может как входить, так и не входить в подмножество.

Порождение всех подмножеств эквивалентно порождению всех n-разрядных двоичных наборов: a_i принадлежит подмножеству множества A тогда и только тогда, когда i-й разряд равен 1. В свою очередь задача порождения случайного подмножества сводится к задаче порождения случайного двоичного набора длины n, то есть случайного числа в диапазоне от 0 до 2n – 1.

Наиболее очевидным способом порождения всех двоичных наборов длины n является счет в системе счисления с основанием 2. При этом два последовательных подмножества могут значительно отличаться друг от друга количеством и составом элементов, что соответствует появлению старшего разряда в очередном двоичном числе.

Рассмотрим следующую задачу.

Дипломатия. На дипломатический раунд в специально оборудованном помещении собрались представители N держав. Организаторы встречи знают, что ряд вопросов должен обсуждаться в узком кругу участников. Некоторые документы могут готовиться представителем единственной страны. В то же время ряд решений принимается без участия представителя какой-либо страны (например, последствия ядерной программы Ирана могут обсуждаться без представителя Ирана). Не владея всеми тайнами дипломатии, организаторы решили обеспечить всевозможные сочетания участников встречи, вызывая некоторых дипломатов в другое помещение для оформления пропусков и возвращая их обратно. Необходимо вызывать и возвращать дипломатов по одному человеку, в противном случае может возникнуть дипломатический скандал. Помогите организаторам справиться с этой проблемой.

Эта задача решается путем использования кодов Грея. Наименьшим возможным изменением при переходе от одного подмножества к другому является добавление или удаление одного элемента множества. В терминах двоичных наборов это означает, что последовательные наборы должны различаться в одном разряде. Такие последовательности двоичных наборов называются кодами Грея. Более точно: n-разрядный код Грея есть упорядоченная циклическая последовательность из 2ⁿ n-разрядных наборов (кодовых слов), такая, что последовательные кодовые слова различаются в одном разряде. Обычно начальным кодовым словом считают (0, 0, …, 0), хотя на самом деле это несущественно, поскольку код циклический.

Существует много n-разрядных кодов Грея. Рассмотрим один из них. Предположим, что

G0

G1

G(n) = …

GM,

где M = 2n - 1, есть n-разрядный код Грея, записанный в виде матрицы 2n ´ n так, что i-я строка матрицы является i-м кодовым словом. Тогда

0G0

0G1

…

0GM

G(n+1) = 1GM

1GM-1

…

1G1

1G0

очевидно, есть (n+1)-разрядный код Грея. По этому рекурсивному определению

G(1) = 0

G(2) = 01

G(3) = 010

Можно определить (n+1)-разрядный код Грея иначе:

G00

G01

G11

G(n+1) = G10

G20

G21

…

…

Легко проверить, что таким образом получается тот же самый код Грея. Это рекурсивное определение близко к рекурсивному определению двоичного представления целых чисел. Действительно, если

0 B0

1 B1

2 B2

… = …

… …

2n -1 BM

то

0 B00

1 B01

2 B10

3 = B11

… …

2n+1 -2 BM0

2n+1 -1 BM1

Это позволяет предложить способ получения Gi из двоичного представления числа i. Если

i = (bn bn-1 …b0)2, то

Gi = (gn gn-1 …g1)2, где

gj = bj + bj-1 (mod 2), 1 ≤ j ≤ n.

Последнее равенство дает возможность вычислить номер кодового слова Gi по его представлению. Пусть i = (bn bn-1 …b0)². Тогда

n

bj = Σ gm (mod 2), 1 ≤ j ≤ n.

m=j+1

Сложение двух разрядов по модулю 2 то же самое, что исключающее " или” (XOR), поэтому можно просто сдвинуть разряды i на одну позицию влево и выполнить операцию исключающего " или”:

bn bn-1 … b2 b1 b0

bn bn-1 bn-2… b1 b0

gn gn-1 … g2 g1

Приведенные формулы позволяют перечислить нерекурсивно кодовые слова Грея заданной размерности n, изменяя i от 0 до 2n –1 и получая по двоичному представлению i разряды кодового слова Gi. Аналогично, если взять случайное число i в диапазоне от 0 до 2n –1, то по нему легко восстанавливается случайное кодовое слово Gi.

Пусть, например, n = 3, а i = 5 = (0101)2. Тогда операция XOR дает:

0 1 0 1

0 1 0 1

1 1 1,

что соответствует кодовому слову G5. В качестве проверки выполним обратное преобразование разрядов кодового слова G5 в двоичные разряды i, в результате которого получим i = (0101)2 = 5.

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

Рассмотрим еще одну распространенную задачу. Пусть задано множество {a1, a2, …, an}. Рассмотрим порождение в лексикографическом порядке подмножеств из k элементов, то есть сочетаний из n предметов по k штук. Как и ранее можно считать, что подмножество определяется последовательностью индексов располагаемых элементов, поэтому будем выбирать подмножества множества {1, 2, …, n}.

Например, трехэлементные подмножества множества {1, 2, 3, 4, 5, 6} записываются в лексикографическом порядке следующим образом:

123 135 234 256

124 136 235 345

125 145 236 346

126 146 245 356

134 156 246 456

Подмножества или сочетания в лексикографическом порядке можно порождать простым способом. Начиная с сочетания (1, 2, …, k) следующее сочетание находится просмотром текущего сочетания справа налево с тем, чтобы определить место самого правого элемента, который еще не достиг максимального значения. Этот элемент увеличивается на 1. Всем элементам справа от него присваиваются новые наименьшие возможные значения, которые должны быть больше данного элемента.