Алгоритм взят из книги Теоретический минимум по Computer Science. Алгоритм итеративный и очень простой для понимания.
На изображении пример работы алгоритма для множества [1, 2, 3].
1 2 3 4 5 6 7 8 9 10 | результат = множество содержащие в себе пустое множество Для каждого элемента x из исходного множества копия_результата = копировать результат # в каждый элемент копии добавляем элемент исходного множества Для каждого элемента y из копия_результата y = y + x # Объединяем результат и копию результат = результат + копия_результата |
Каждый элемент исходного множества увеличивает результирующее множества в 2 раза. В итоге множество всех подмножеств будет содержать \(2^n\) элементов, где n — количество элементов исходного множества.
Пример на Python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | 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)) |
