如何得到集合的所有子集？（动力装置）

Question

给定一组

{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

Python^{} page正好有一个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长度的组合。

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]

Mark Rushakoff的注释适用于这里：“如果您不喜欢开头的空元组，打开。”您只需将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上搜索了“python power set”，然后找到了这个：Python Power Set Generator

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

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