如何获得集合的所有子集？(Powerset)

Question

如何获得集合的所有子集？(Powerset)给定一组{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}]

Answer 1

Pythonitertools页有一个powerset这方面的配方：

from itertools import chain, combinationsdef 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长度的组合。

Answer 2

下面是Powerset的更多代码。这是从头开始写的：

>>> 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语句更改为range(1，len(S)+1)，以避免0长度的组合”，除非在我的例子中更改。for i in range(1 << x)到for i in range(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意味着不需要计算单个内存中的所有结果。在主循环外重新计算掩码被认为是一个有价值的优化。

Answer 3

如果您正在寻找一个快速的答案，我刚刚在Google上搜索了“pythonpowerset”，并得到了如下结果：Python功率集生成器

下面是页面中代码的复制粘贴：

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]]