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

Question

如何找到一组的所有子集，只有n个元素？我正在用Python编写程序，我意识到我需要解决的一个问题需要我，给定一个S带n元素（| S | = n）的集合来测试某个顺序的所有可能子集上的函数m（即m元素数量）。要使用答案生成部分解，然后再次使用下一个阶m = m + 1，直到m = n。我正在编写表单的解决方案：def findsubsets(S, m):     subsets = set([])     ...     return subsets但是知道Python我希望解决方案已经存在。完成此任务的最佳方法是什么？

Answer 1

使用规范函数从itertools配方页面获取powerset：

from itertools import chain, combinationsdef 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])

Answer 2

这是一个单行，它为您提供整数[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)]