我正在尝试实现一个函数来生成列表xs
的幂集。
一般的想法是,我们遍历xs
的元素,并选择是否包含x
。我面临的问题是withX
最终等于[None]
(带有None
的单例列表),因为(我认为)s.add(x)
返回None
。
这不是家庭作业,而是破解编码面试的练习。
def powerSetBF(xs):
powerSet = []
powerSet.append(set([]))
for x in xs:
powerSetCopy = powerSet[:]
withX = [s.add(x) for s in powerSetCopy] # add x to the list of sets
powerSet = powerSet.extend(withX) # append those entries
return powerSet
看看itertools
食谱中的powerset
示例:
from itertools import chain, combinations
def powerset(iterable):
"list(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))
对于不超过给定列表长度的整数range
,请尽可能combinations
并将它们作为一个对象chain
在一起。
这是一个不使用任何模块的递归解决方案:
def pset(myset):
if not myset: # Empty list -> empty set
return [set()]
r = []
for y in myset:
sy = set((y,))
for x in pset(myset - sy):
if x not in r:
r.extend([x, x|sy])
return r
print(pset(set((1,2,3,4))))
#[set(), {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4},
# {1, 4}, {2, 4}, {1, 2, 4}, {3, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}]
import itertools
def powerset(L):
pset = set()
for n in xrange(len(L) + 1):
for sset in itertools.combinations(L, n):
pset.add(sset)
return pset
powerset([1, 2, 3, 4])
结果
set([(1, 2), (1, 3), (1, 2, 3, 4), (1,), (2,), (3,), (1, 4), (4,), (), (2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3), (3, 4), (2, 4)])
itertools.combinations
的源代码可以在这里找到,其中有一些简洁的优化:
https://docs.python.org/3/library/itertools.html#itertools.combinations