如何找到一組的所有子集，只有n個元素？我正在用Python編寫程序，我意識到我需要解決的一個問題需要我，給定一個S帶n元素（| S | = n）的集合來測試某個順序的所有可能子集上的函數(shù)m（即m元素數(shù)量）。要使用答案生成部分解，然后再次使用下一個階m = m + 1，直到m = n。我正在編寫表單的解決方案：def findsubsets(S, m):
subsets = set([])
...
return subsets但是知道Python我希望解決方案已經(jīng)存在。完成此任務(wù)的最佳方法是什么？
3 回答
撒科打諢
TA貢獻1934條經(jīng)驗 獲得超2個贊
使用規(guī)范函數(shù)從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])
慕虎7371278
TA貢獻1802條經(jīng)驗 獲得超4個贊
這是一個單行，它為您提供整數(shù)[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)]
添加回答
舉報
0/150
提交
取消