如何获取一个集合的所有子集？（幂集）

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 幂集”，找到了这个链接：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]]

Answer 2

这里有更多关于幂集的代码。这段代码是从头开始写的：

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

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的组合了。