如何找到一组的所有子集,只有n个元素？

我正在用Python编写程序,我意识到我需要解决的一个问题需要我,给定一个S带n元素(| S | = n)的集合来测试某个顺序的所有可能子集上的函数m(即m元素数量).要使用答案生成部分解,然后再次使用下一个阶m = m + 1,直到m = n.

我正在编写表单的解决方案:

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

但是知道Python我希望解决方案已经存在.

完成此任务的最佳方法是什么？

1> recursive..：

---

如果你有Python 2.6或更高版本,itertools.combinations是你的朋友.否则,请检查链接以获取等效函数的实现.

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

S:要查找子集的集合
m:子集中的元素数量

---

我不会返回一个集合,但只是返回迭代器(或者只是使用combination()而不定义findsubsets()......)

2> brice..：

---

使用规范函数从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)]

如果你想要映射到集合你可以使用union,intersection等...:

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

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

---

有用的公式,但使用`chain.from_iterable`而不是星形扩展可能非常长的集合.将组合迭代到一个列表(`[...]`),星形扩展,链接到迭代器(`链`),然后变成列表_again_是什么意思？PS.更好的配方是在`itertools`文档中,在另一个(稍后)回答这里.