如何找到一组的所有子集,只有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

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

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

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

Answer 2

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

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

Answer 4

这是一种易于理解的算法的巧妙方法。

import copy

nums = [2,3,4,5]
subsets = [[]]

for n in nums:
    prev = copy.deepcopy(subsets)
    [k.append(n) for k in subsets]
    subsets.extend(prev)

print(subsets) 
print(len(subsets))

# [[2, 3, 4, 5], [3, 4, 5], [2, 4, 5], [4, 5], [2, 3, 5], [3, 5], [2, 5], [5], 
# [2, 3, 4], [3, 4], [2, 4], [4], [2, 3], [3], [2], []]

# 16 (2^len(nums))