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

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

Алгоритм взят из книги Теоретический минимум по Computer Scienceopen in new window (Лабиринтopen in new window, ЛитРесopen in new window). Алгоритм итеративный и очень простой для понимания.

На изображении пример работы алгоритма для множества [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
Последниее изменение: 13.09.2021, 14:02:47