在Python中获取集合的子集

Question

假设我们需要写一个函数，来列出一个集合的所有子集。下面给出了这个函数和一个测试用例。我们需要完成这个函数的全部定义。

def subsets(s):
   """Return a list of the subsets of s.

   >>> subsets({True, False})
   [{False, True}, {False}, {True}, set()]
   >>> counts = {x for x in range(10)} # A set comprehension
   >>> subs = subsets(counts)
   >>> len(subs)
   1024
   >>> counts in subs
   True
   >>> len(counts)
   10
   """
   assert type(s) == set, str(s) + ' is not a set.'
   if not s:
       return [set()]
   element = s.pop() 
   rest = subsets(s)
   s.add(element)    

---

这个函数不能使用任何内置函数。

我的想法是把“元素”加到其他部分中，然后把它们全部返回，但我对在Python中如何使用集合和列表不是很熟悉。

Answer 1

通常情况下，求一个列表的所有子集（也叫幂集）的方法大致是这样的：

def powerset(elements):
    if len(elements) > 0:
        head = elements[0]
        for tail in powerset(elements[1:]):
            yield [head] + tail
            yield tail
    else:
        yield []

只需要稍微调整一下，就可以处理集合（set）了。

Answer 2

在编程中，有时候我们会遇到一些问题，特别是在使用某些工具或库的时候。这些问题可能会让我们感到困惑，但其实很多时候，解决方案就在我们身边。我们只需要仔细查看错误信息，或者在网上搜索一下，就能找到答案。

比如说，当你在运行代码时，如果出现了错误，通常会有一段提示信息告诉你哪里出了问题。这个提示信息就像是一个指南，帮助你找到解决问题的方法。

另外，很多编程问题其实已经被别人遇到过并解决了。你可以在像StackOverflow这样的网站上搜索相关问题，看看其他人是怎么解决的。这不仅能节省你的时间，还能让你学到新的知识。

总之，遇到问题时不要慌张，仔细分析错误信息，善用网络资源，很多时候你会发现解决方案比你想象的要简单得多。

>>> s=set(range(10))
>>> L=list(s)
>>> subs = [{L[j] for j in range(len(L)) if 1<<j&i} for i in range(1,1<<len(L))]
>>> s in subs
True
>>> set() in subs
False

Answer 3

看看 powerset() 这个方法在 itertools 文档里的介绍。

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

def subsets(s):
    return map(set, powerset(s))