9. Подмножества множеств
Пусть имеется множество A={a1, a2, …, an}. Имеется 2n подмножеств этого множества. Действительно, каждый из элементов независимо от других может как входить, так и не входить в подмножество.
Порождение всех подмножеств эквивалентно порождению всех n-разрядных двоичных наборов: ai принадлежит подмножеству множества A тогда и только тогда, когда i-й разряд равен 1. В свою очередь задача порождения случайного подмножества сводится к задаче порождения случайного двоичного набора длины n, то есть случайного числа в диапазоне от 0 до 2n – 1.
Наиболее очевидным способом порождения всех двоичных наборов длины n является счет в системе счисления с основанием 2. При этом два последовательных подмножества могут значительно отличаться друг от друга количеством и составом элементов, что соответствует появлению старшего разряда в очередном двоичном числе.
Рассмотрим следующую задачу.
Дипломатия. На дипломатический раунд в специально оборудованном помещении собрались представители N держав. Организаторы встречи знают, что ряд вопросов должен обсуждаться в узком кругу участников. Некоторые документы могут готовиться представителем единственной страны. В то же время ряд решений принимается без участия представителя какой-либо страны (например, последствия ядерной программы Ирана могут обсуждаться без представителя Ирана). Не владея всеми тайнами дипломатии, организаторы решили обеспечить всевозможные сочетания участников встречи, вызывая некоторых дипломатов в другое помещение для оформления пропусков и возвращая их обратно. Необходимо вызывать и возвращать дипломатов по одному человеку, в противном случае может возникнуть дипломатический скандал. Помогите организаторам справиться с этой проблемой.
Эта задача решается путем использования кодов Грея. Наименьшим возможным изменением при переходе от одного подмножества к другому является добавление или удаление одного элемента множества. В терминах двоичных наборов это означает, что последовательные наборы должны различаться в одном разряде. Такие последовательности двоичных наборов называются кодами Грея. Более точно: n-разрядный код Грея есть упорядоченная циклическая последовательность из 2n 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)-разрядный код Грея. По этому рекурсивному определению1
00G(2) = 01
11
10
000
001
011
G(3) = 010
110
111
101
100
Можно определить (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)2. Тогда
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. Всем элементам справа от него присваиваются новые наименьшие возможные значения, которые должны быть больше данного элемента.
Задачи для самостоятельного решения
9.1. Простые примеры на подмножества (3)- Составить программы для решения следующих задач:
выдать слова кода Грея заданной размерности, используя рекурсию и генерацию слов по их номерам;
задано множество символов, выдать его подмножества из заданного числа элементов в лексикографическом порядке;
- Входные данные задавать с клавиатуры, вывод результатов - на экран.