我怎样才能找到一个集合的所有子集，正好有n个元素？

Question

我正在用Python编写一个程序，我意识到我需要解决的一个问题需要我，给定一组S和n元素（| S |=n），在某个顺序的所有可能子集上测试一个函数m（即元素数m）。要使用答案生成部分解，然后按下一个顺序m=m+1重试，直到m=n

我正在写一份表格的解决方案：

def findsubsets(S, m):
    subsets = set([])
    ...
    return subsets

但了解了Python，我希望已经有了解决方案。

实现这一目标的最佳方法是什么？

Answer 1

这里有一行代码，它给出整数的所有子集[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)]

Answer 2

使用规范函数从the itertools recipe页获取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])

Answer 3

如果你有Python2.6或更高版本，那么itertools.combinations就是你的朋友。否则，请检查链接以获取等效函数的实现。

import itertools
def findsubsets(S,m):
    return set(itertools.combinations(S, m))

S：要查找其子集的集合
m： 子集中的元素数