Алгоритм генерации всех подмножеств

Алгоритм взят из книги «Теоретический минимум по Computer Science». Алгоритм итеративный и очень простой для понимания.

На изображении пример работы алгоритма для множества [1, 2, 3].

Генерация всех подмножеств

результат = множество содержащие в себе пустое множество
Для каждого элемента x из исходного множества 
  копия_результата = копировать результат

  # в каждый элемент копии добавляем элемент исходного множества
  Для каждого элемента y из копия_результата
    y = y + x

  # Объединяем результат и копию
  результат = результат + копия_результата

1
2
3
4
5
6
7
8
9
10

Каждый элемент исходного множества увеличивает результирующее множества в 2 раза. В итоге множество всех подмножеств будет содержать [latex]2^n[/latex] элементов, где n — количество элементов исходного множества.

Пример на Python:

import copy

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

def get_subsets(main):
    result = [[]]

    for main_element in main:
        new_set = copy.deepcopy(result)
        for item in new_set:
            item.append(main_element)
        result += new_set

    return result

print(get_subsets(main_set))

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

# Алгоритм генерации всех подмножеств

Алгоритм генерации всех подмножеств