Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.74/76: Рейтинг темы: голосов - 76, средняя оценка - 4.74
1 / 1 / 0
Регистрация: 29.03.2015
Сообщений: 1
1

Генерация подмножеств множества(Бинарный код)

29.03.2015, 11:33. Показов 14359. Ответов 2
Метки нет (Все метки)


Алгоритмы теории множеств нередко применяются в программировании. В этой статье я хочу поговорить о генерации подмножеств множества. Множество — это набор элементов. Все элементы множества различны, то есть один элемент не может встретиться в множестве дважды. Программно реализовать множество можно разными способами: в виде класса, в виде массива с функциями для операций над ним и т.д. В языке 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, на каждой итерации представить значение счетчика в виде бинарного кода, на основе его составить подмножество. Реализация на Си:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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, использовать его как битовую маску и сгенерировать на ее основе подмножество. Удачного программирования!


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

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

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.03.2015, 11:33
Ответы с готовыми решениями:

Генерация всех подмножеств данного множества
Друзья, помогите написать программку в консольном приложении VS 2008, задание такое: Генерация...

Разбиение множества S на M подмножеств
Когда я прописываю числа S и M константами все идеально работает, в противном случае нет. ...

Перебор всех возможных подмножеств множества целых чисел
Всем привет)))) Пожалуйста, помогите решить задачку!!!!! Очень нужно, срочно!!! Программа...

Поиск подмножеств множества чисел, обладающих заданными свойствами;
Имеется N различных натуральных чисел. Определите подмножество данных чисел, дающих в сумме число...

2
0 / 0 / 0
Регистрация: 05.12.2017
Сообщений: 8
09.03.2018, 20:06 2
а если порядок важен?
0
0 / 0 / 0
Регистрация: 23.02.2018
Сообщений: 38
13.04.2019, 12:43 3
А теперь скажите мне пожалуйста, как это должно выглядеть на C#? Особенно, если я хочу передать в некоторый двумерный массив все возможные подмножества длиною 2, подмножество соответственно будет вложено в такой массив так:первый элемент в "строке" 0, второй - в" строке" 1.
Спасибо!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.04.2019, 12:43

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Перебор всех возможных подмножеств заданного множества целых чисел
Помогите решить задачу. Есть заданное множество целых чисел: -1 0 1. Нужно перебрать все возможные...

Генерация всех подмножеств множества
Создать програму которая будет генерировать все подмножества множества

Генерация к-подмножеств из множества с n элементами
Ребят, такой вопрос, не могу переделать код c Pascal на C. Генерация k-подмножеств из множества с n...

Генерация всех подмножеств заданного n-элементного множества
помогите найти ошибку в коде задание было &quot;Генерировать все подмножества заданного N-элементного...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.