@Immortal_Vital

Алгоритмы теории множеств нередко применяются в программировании. В этой статье я хочу поговорить о генерации подмножеств множества. Множество — это набор элементов. Все элементы множества различны, то есть один элемент не может встретиться в множестве дважды. Программно реализовать множество можно разными способами: в виде класса, в виде массива с функциями для операций над ним и т.д. В языке Pascal имеется готовая реализация и синтаксис для работы со множествами.
Генерация подмножеств множества может пригодиться, допустим, в логике игры, когда из набора персонажей необходимо выбрать случайную их группу. Допустим, имеется множество M = {1, 2, 3}. Все подмножества множества M (их совокупность называют булеаном) следующие:
{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
Первым в списке идет пустое множество, которое является подмножеством любого множества. Последний — исходное множество (множество является подмножеством самого себя).
Существует величина мощность множества, характеризующая количество элементов множества. Так вот, количество подмножеств множества можно вычислить по формуле 2^n, где n — мощность множества. У множества M количество подмножеств равно 2^3 = 8, в чем можно убедиться, посчитав их .
Программно сгенерировать все подмножества множества, на самом деле, очень просто. Например, можно воспользоваться Кодом Грея. Но есть способ еще проще, в основе которого лежит бинарный или двоичный код. Рассмотрим числа в диапазоне 0..2^n-1 в двоичной системе счисления с разрядностью n (увеличив при необходимости незначащими нулями):
0: 000
1: 001
2: 010
3: 011
4: 100
5: 101
6: 110
7: 111
Каждый из этих двоичных кодов можно использовать как маску подмножества, то есть, единица в i-ом бите характеризует наличие i-го элемента множества в подмножестве, ноль — отсутствие. Например:
101 = {1, 3}
Таким образом, для генерации подмножеств необходимо организовать цикл от 0 до 2^n-1, на каждой итерации представить значение счетчика в виде бинарного кода, на основе его составить подмножество. Реализация на Си:
результат:
{}
{2}
{5}
{2 5}
{6}
{2 6}
{5 6}
{2 5 6}
{9}
{2 9}
{5 9}
{2 5 9}
{6 9}
{2 6 9}
{5 6 9}
{2 5 6 9}
Порядок, в данном случае, роли не играет. В данном случае мы просто выводим подмножества. Реализация предельно проста и понятна. Единственное, хотелось бы немного остановиться на
if ( i & (1 << j) ) //--если j-й бит установлен
так как думаю, не все понимают, как это работает. Оператор << — это логический сдвиг влево. Чтобы узнать значение j-го бита числа i (биты считаем справа налево, нумерация начинается с нуля) сначала сдвигаем единицу на j. Допустим, i = 18 (10010), j = 2. После логического сдвига влево единицы (00001) на 2 получаем число 00100. Затем мы число i логически умножаем на полученную после сдвига маску. Маска представляет собой совокупность нулей с установленным в единицу j-м битом (благодаря сдвигу). При умножении, если j-й бит в числе i равен единице, мы получим какое-то число (если быть точным, мы получим число равное маске), если j-й бит равен нулю, то результат умножения будет нулем:
10010 *
00100
Побитово умножив два числа (логическая операция and) получим число 00000, что говорит о том, что 2-й бит числа 18 (смотрим порядок нумерации битов) выставлен в ноль. Надеюсь, объяснил более или менее понятно.
Данный алгоритм позволяет очень просто сгенерировать случайное подмножество множества. Как вы уже догадались, для этого нужно всего лишь взять случайное число в диапазоне 0..2^n-1, использовать его как битовую маску и сгенерировать на ее основе подмножество. Удачного программирования!


Как быстро работает этот алгоритм?
Как и все, зависит от параметров. В данном случае, от мощности множества. Алгоритму требуется w * 2^w итераций. Опять же, многое зависит от того, какие операции производить с подмножествами. В общем, думаю, с множеством до 15-20 элементов можно работать (на глаз).
Да, на практике генерировать все подмножества множества (тем более, крупного) вряд ли приходится, более реальная задача - отобрать несколько случайных подмножеств, с чем алгоритм справляется на ура.

Ps: Статья не моя, автора не знаю(

Вернуться к обсуждению:
Генерация подмножеств множества(Бинарный код) C++

1