Описание тега powerset

Для заданного множества S: Powerset Р(S) множество всех подмножеств этого множества S.

• P(S) = {T: T ⊆ S), где T - множество.

Учитывая набор из трех элементов {1, 2, 3}, набор мощности P({1, 2, 3}) будет содержать восемь подмножеств набора, включая себя и пустой набор:

• {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

Для набора S конечного размера n размер набора мощности P(S) равен 2ⁿ. Мощность S всегда строго меньше мощности P(S): множество натуральных чисел N счетно бесконечно, но множество степеней N несчетно.

Алгоритм создания Powerset

Python предлагает itertools, которые можно использовать для создания набора мощности для данного набора или списка. Вот документация: https://docs.python.org/3/library/itertools.html

def powerset(s: set):
    s = list(s)
    ps = chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))
    return list(ps) # set(ps) also works

Вот пробный запуск:

s = {1,2,3}
ps = powerset(s)
# ps = [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Существует итеративный метод создания набора мощности. Размер набора мощности растет экспоненциально и достигает более двух миллиардов для наборов размером больше 32. Для набора S размера n:

• Создайте изначально пустой список L, который в конечном итоге будет представлять powerset
• Дайте каждому элементу индекс в диапазоне от 0 до n-1.
  • Предположим, у нас есть {A, B, C}. Пусть индекс A равен 0, B равен 1, C равен 2.
• Прокрутите все числа от 0 до 2ⁿ-1 и выразите каждое в двоичной форме.
  • Счетчик цикла i идет от 0 (000 в двоичном формате) до 7 (111 в двоичном формате).
• Создайте подмножество T_i на основе двоичного числа, которое содержит такие элементы, что позиция двоичной цифры индекса элементов для i равна 1.
  • Цифре из единиц соответствует позиция 0, цифре из четверок (третья цифра) - позиция 2.
  • Когда у нас 0, подмножество T₀ - это пустое множество.
  • Когда у нас 5, двоичные цифры 101, цифры с позициями 2 и 0 равны единицам, и поэтому подмножество T₅ равно {A, C}.
• Добавим, что подмножество в исходном списке L.

Подробнее

• Википедия
• set, математический объект и структура данных, которая представляет собой набор уникальных объектов.