Алгоритмы теории множеств нередко применяются в программировании. В этой статье я хочу поговорить о генерации подмножеств множества. Множество — это набор элементов. Все элементы множества различны, то есть один элемент не может встретиться в множестве дважды. Программно реализовать множество можно разными способами: в виде класса, в виде массива с функциями для операций над ним и т.д. В языке 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, на каждой итерации представить значение счетчика в виде бинарного кода, на основе его составить подмножество. Реализация на Си:

#include <stdio.h>
#include <stdlib.h>
//--для возведения в степень
#include <math.h>
 
int main()
{
    int M[4] = {2, 5, 6, 9}; //--множество
    int w = 4; //--кол-во элементов множества
 
    int i, j, n;
 
    n = pow(2, w);
    for ( i = 0; i < n; i++ ) //--перебор битовых маск
    {
        printf("{");
        for ( j = 0; j < w; j++ ) //--перебор битов в маске
            if ( i & (1 << j) ) //--если j-й бит установлен
               printf("%d ", M[j]); //--то выводим j-й элемент множества
        printf("}\n");
    }
    return 0;
}

результат:

{}
{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, использовать его как битовую маску и сгенерировать на ее основе подмножество. Удачного программирования!