Как получить все подмножества набора? (степенное множество)

Учитывая набор

{0, 1, 2, 3}

Как может я производить подмножества:

[set(),
 {0},
 {1},
 {2},
 {3},
 {0, 1},
 {0, 2},
 {0, 3},
 {1, 2},
 {1, 3},
 {2, 3},
 {0, 1, 2},
 {0, 1, 3},
 {0, 2, 3},
 {1, 2, 3},
 {0, 1, 2, 3}]
65
задан astronought 20 September 2019 в 13:22
поделиться

4 ответа

Страница Python itertools имеет точно рецепт powerset для этого:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Вывод :

>>> list(powerset("abcd"))
[(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]

Если вам не нравится этот пустой кортеж в начале, вы можете просто изменить оператор range на range (1, len (s) +1) , чтобы избежать комбинация длины 0.

94
ответ дан 24 November 2019 в 15:15
поделиться
def powerset(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result],
                  lst, [[]])
11
ответ дан 24 November 2019 в 15:15
поделиться

Если вы ищете быстрый ответ, я просто искал «питон питона» в Google и нашел это: генератор питающей установки питона

вот копия- вставьте из кода на этой странице:

def powerset(seq):
    """
    Returns all the subsets of this set. This is a generator.
    """
    if len(seq) <= 1:
        yield seq
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

Это можно использовать следующим образом:

 l = [1, 2, 3, 4]
 r = [x for x in powerset(l)]

Теперь r - это список всех элементов, которые вам нужны, и его можно отсортировать и распечатать:

r.sort()
print r
[[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]
14
ответ дан 24 November 2019 в 15:15
поделиться

Вот еще код для набора мощности. Это написано с нуля:

>>> def powerset(s):
...     x = len(s)
...     for i in range(1 << x):
...         print [s[j] for j in range(x) if (i & (1 << j))]
...
>>> powerset([4,5,6])
[]
[4]
[5]
[4, 5]
[6]
[4, 6]
[5, 6]
[4, 5, 6]

Комментарий Марка Рушакова применим здесь: «Если вам не нравится этот пустой кортеж в начале, дальше», вы можете просто изменить оператор диапазона на range (1, len (s) + 1) чтобы избежать комбинации длины 0 », за исключением того, что в моем случае вы меняете для i в диапазоне (1 << x) на для i в диапазоне (1, 1 << x) .


Возвращаясь к этому годы спустя, я бы теперь написал это так:

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        yield [ss for mask, ss in zip(masks, s) if i & mask]

И тогда тестовый код будет выглядеть так, скажем:

print(list(powerset([4, 5, 6])))

Использование yield означает, что вы нет необходимости вычислять все результаты в одном фрагменте памяти. Предполагается, что предварительное вычисление масок вне основного цикла будет стоящей оптимизацией.

35
ответ дан 24 November 2019 в 15:15
поделиться
Другие вопросы по тегам:

Похожие вопросы: