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

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Пусть имеется множество 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-разрядных кодов Грея. Рассмотрим один из них. Предположим, что

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

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

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

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

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

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

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

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

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

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

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

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

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

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