什么是通过一套组合的好方法？
给定一套
{a,b,c,d} 什么是生产的好方法
{a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,bcd,abcd}
？
Python itertools页面有一个powerset配方：
def powerset(iterable): "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
输出：
>>> list(powerset("abcd")) [(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]
如果你在开始时不喜欢这个空元组，你可以将range语句改为range(1, len(s)+1)以避免0长度的组合。
这是一个powerset的更多代码。 这是从头开始写的：
>>> def powerset(s): ... x = len(s) ... for i in range(1 << x): ... print [s[j] for j in range(x) if (i & (1 << j))] ... >>> powerset([4,5,6]) [] [4] [5] [4, 5] [6] [4, 6] [5, 6] [4, 5, 6]
Mark Rushakoff的评论在这里是适用的：“如果你在开始时不喜欢那个空元组，你可以将范围语句改为范围（1，len（s）+1），以避免0长度的组合“，除了在我的情况下，你for i in range(1 << x)改变for i in range(1, 1 << x) 。
回到这几年后，我现在写这样的：
def powerset(s): x = len(s) masks = [1 << i for i in range(x)] for i in range(1 << x): yield [ss for mask, ss in zip(masks, s) if i & mask]
然后testing代码看起来像这样，说：
print(list(powerset([4, 5, 6])))
使用yield意味着你不需要在单个内存中计算所有的结果。 在主回路之外预先计算掩模被认为是一个有价值的优化。
如果你正在寻找一个快速的答案，我刚刚在谷歌search“python power set”，并提出了这个： Python Power Set Generator
以下是该页面中代码的复制粘贴：
def powerset(seq): """ Returns all the subsets of this set. This is a generator. """ if len(seq) <= 1: yield seq yield [] else: for item in powerset(seq[1:]): yield [seq[0]]+item yield item
这可以像这样使用：
l = [1, 2, 3, 4] r = [x for x in powerset(l)]
现在r是你想要的所有元素的列表，可以sorting和打印：
r.sort() print r [[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]
def powerset(lst): return reduce(lambda result, x: result + [subset + [x] for subset in result], lst, [[]])
有一个权力的提炼：
def powerset(seq): """ Returns all the subsets of this set. This is a generator. """ if len(seq) <= 0: yield [] else: for item in powerset(seq[1:]): yield [seq[0]]+item yield item
def get_power_set(s): power_set=[[]] for elem in s: # iterate over the sub sets so far for sub_set in power_set: # add a new subset consisting of the subset at hand added elem power_set=power_set+[list(sub_set)+[elem]] return power_set
例如：
get_power_set([1,2,3])
产量
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
我只是想提供最易懂的解决scheme，反码高尔夫版本。
from itertools import combinations l = ["x", "y", "z", ] def powerset(items): combo = [] for r in range(len(items) + 1): #use a list to coerce a actual list from the combinations generator combo.append(list(combinations(items,r))) return combo l_powerset = powerset(l) for i, item in enumerate(l_powerset): print "All sets of length ", i print item
结果
所有的长度为0
[()]
所有套的长度1
[('x',), ('y',), ('z',)]
所有套的长度2
[('x', 'y'), ('x', 'z'), ('y', 'z')]
所有套的长度3
[('x', 'y', 'z')]
欲了解更多信息， 请参阅itertools文档 ，也是权力集维基百科条目
这是疯狂的，因为这些答案都没有提供实际Python集合的返回。 这是一个混乱的实现，会给一个实际上是Python set的powerset。
test_set = set(['yo', 'whatup', 'money']) def powerset( base_set ): """ modified from pydoc's itertools recipe shown above""" from itertools import chain, combinations base_list = list( base_set ) combo_list = [ combinations(base_list, r) for r in range(len(base_set)+1) ] powerset = set([]) for ll in combo_list: list_of_frozensets = list( map( frozenset, map( list, ll ) ) ) set_of_frozensets = set( list_of_frozensets ) powerset = powerset.union( set_of_frozensets ) return powerset print powerset( test_set ) # >>> set([ frozenset(['money','whatup']), frozenset(['money','whatup','yo']), # frozenset(['whatup']), frozenset(['whatup','yo']), frozenset(['yo']), # frozenset(['money','yo']), frozenset(['money']), frozenset([]) ])
不过，我希望看到更好的实施。
这是我使用组合的快速实现，但只使用内置。
def powerSet(array): length = str(len(array)) formatter = '{:0' + length + 'b}' combinations = [] for i in xrange(2**int(length)): combinations.append(formatter.format(i)) sets = set() currentSet = [] for combo in combinations: for i,val in enumerate(combo): if val=='1': currentSet.append(array[i]) sets.add(tuple(sorted(currentSet))) currentSet = [] return sets
我发现以下algorithm非常清晰和简单：
def get_powerset(some_list): """Returns all subsets of size 0 - len(some_list) for some_list""" if len(some_list) == 0: return [[]] subsets = [] first_element = some_list[0] remaining_list = some_list[1:] # Strategy: get all the subsets of remaining_list. For each # of those subsets, a full subset list will contain both # the original subset as well as a version of the subset # that contains first_element for partial_subset in get_all_subsets(remaining_list): subsets.append(partial_subset) subsets.append(partial_subset[:] + [first_element]) return subsets
另一种可以生成powerset的方法是生成所有具有n位的二进制数。 作为功率设置，具有n数字的数量是2 ^ n 。 这个algorithm的原理是一个元素可以存在或不在一个子集中，因为二进制数字可以是一个或零，但不能同时存在。
def power_set(items): N = len(items) # enumerate the 2 ** N possible combinations for i in range(2 ** N): combo = [] for j in range(N): # test bit jth of integer i if (i >> j) % 2 == 1: combo.append(items[j]) yield combo
当我使用MITx：6.00.2x计算思维和数据科学简介时，我发现了两种algorithm，我认为这是我所见过的最简单的algorithm之一。
""" from https://docs.python.org/3.6/library/itertools.html uses the module itertools chaining together the two functions combinations() and chain() is faster than iterating and generator functions in Python Author: joltE Date: 3/15/2017 """ def powerset(iterable): "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" from itertools import chain, combinations s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) def AllCombo(items): return [list(i) for i in powerset(items)]
试验台
print(AllCombo([1, 3, 5, 7])) print([list(i) for i in powerset([1, 3, 5, 7])])
powerset（）就像一个生成器函数，但是由于只使用了itertools内置函数chain（）和combinations（），效率更高。 powerset（）输出元组，这可以转换为列表，就像在AllCombo中用list（）函数所做的那样。 testing平台中的两个打印语句都输出相同的数据。
