我怎样才能find一个集合的所有子集，正好有n个元素？
我正在用Python编写一个程序，并且我意识到我需要解决的一个问题是给定一个具有n元素（| S | = n）的集合S来testing一个特定阶m所有可能子集的函数即具有m个元素）。 要使用答案产生部分解，然后再次尝试下一个阶m = m + 1，直到m = n。
我正在写一个表单的解决scheme：
def findsubsets(S, m): subsets = set([]) ... return subsets
但是，我知道Python我期望一个解决scheme已经在那里。
什么是完成这个最好的方法？
itertools.combinations是你的朋友，如果你有Python 2.6或更高。 否则，请检查链接以获取等效函数的实现。
import itertools def findsubsets(S,m): return set(itertools.combinations(S, m))
使用规范函数从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) """ xs = list(iterable) # note we return an iterator rather than a list return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))
用于：
>>> list(powerset("abc")) [(), ('a',), ('b',), ('c',), ('a', 'b'), ('a', 'c'), ('b', 'c'), ('a', 'b', 'c')] >>> list(powerset(set([1,2,3]))) [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
映射到集，如果你想，所以你可以使用联合，交集等…：
>>> map(set, powerset(set([1,2,3]))) [set([]), set([1]), set([2]), set([3]), set([1, 2]), set([1, 3]), set([2, 3]), set([1, 2, 3])] >>> reduce(lambda x,y: x.union(y), map(set, powerset(set([1,2,3])))) set([1, 2, 3])
这是一个单线程，给你所有的整数子集[0..n]，而不仅仅是给定长度的子集：
from itertools import combinations, chain allsubsets = lambda n: list(chain(*[combinations(range(n), ni) for ni in range(n+1)]))
所以例如
>> allsubsets(3) [(), (0,), (1,), (2,), (0, 1), (0, 2), (1, 2), (0, 1, 2)]
这是一些伪代码 – 您可以通过随时随地存储每个调用的值，并在recursion调用之前（如果调用值已经存在）来裁减相同的recursion调用。
以下algorithm将具有排除空集的所有子集。
list * subsets(string s, list * v) { if(s.length() == 1) { list.add(s); return v; } else { list * temp = subsets(s[1 to length-1], v); int length = temp->size(); for(int i=0;i<length;i++) { temp.add(s[0]+temp[i]); } list.add(s[0]); return temp; } }
所以，例如，如果s =“123”，那么输出是：
1 2 3 12 13 23 123
不使用itertools ：
在Python 3中，您可以使用yield from来添加一个子集生成器方法来插入集类：
class SetWithSubset(set): def subsets(self): s1 = [] s2 = list(self) def recfunc(i=0): if i == len(s2): yield frozenset(s1) else: yield from recfunc(i + 1) s1.append(s2[ i ]) yield from recfunc(i + 1) s1.pop() yield from recfunc()
例如下面的代码片段按预期工作：
x = SetWithSubset({1,2,3,5,6}) {2,3} in x.subsets() # True set() in x.subsets() # True x in x.subsets() # True x|{7} in x.subsets() # False set([5,3]) in x.subsets() # True - better alternative: set([5,3]) < x len(x.subsets()) # 32
