Генерация всех подмножеств с помощью двоичного представления числа

Другой варианта алгоритма генерации всех подмножествopen in new window. Сначала пример.

Дано множество из 5 элементов.

[1, 2, 3, 4, 5]

Возьмём пятизначное двоичное число и поставим в соответствие каждой цифре этого числа один из элементов исходного множества. Таким способом мы можем задавать подмножества исходного пятиэелементного множества.

10101 = [1, 3, 5]
00011 = [4, 5]
00000 = []

1
2
3

Если взять все числа от 00000 до 11111 то они будут соответствовать всем подмножествам исходного множества. В десятичной системе эти числа соответствуют числам от 0 до [latex]2^5 - 1[/latex].

Исходя из этих размышлений, формируем алгоритм:


# функция возвращает множество  
# из элементов set отмеченных единицей в mask
get_elements(set, mask)

n = длина исходного множества
result = пустое множество
Для каждого i в диапазоне от 0 до 2**n - 1
  bits = число i в двоичной форме
  new_element = get_elements(исходное множество, bits)
  добавить new_element в result

1
2
3
4
5
6
7
8
9
10
11

Реализация на Python

source_set = [1, 2, 3]
print(source_set)

def get_elements(source, mask):
    result = []
    for n in range(len(source)):
        if mask & 1 == 1:
            result.append(source[n])
        mask = mask >> 1
    return result

def power_set(source):
    result = []

    for i in range(2 ** len(source)):
        result.append(get_elements(source, i))

    return result

print(power_set(source_set))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Для работы с битам используются битовые операцииopen in new window с целыми числами.

# Генерация всех подмножеств с помощью двоичного представления числа

Генерация всех подмножеств с помощью двоичного представления числа