用Python中的递归和Yield语句生成功率集

Question

我对Python有点陌生，正在进行编程练习。我已经编写了以下递归方法来基于Python中的输入列表生成幂集。它应该返回一个生成器，该生成器生成作为s传入的给定列表的幂集。功率集中的每个元素都应该是一个集合。

def gps(s, res=set()):
if s:
elem = s.pop()
gps(s, res)
res.add(elem)
gps(s, res)
else:
yield res

当我使用list(gps([1,2]))调用它时，它会给我[]。正确的结果应该类似于[set(), {1}, {2}, {1, 2}]。

我删除了yield语句，添加了两行代码，并反复使用print语句来获得这段代码，它打印出了正确的结果，看起来更近了一步：

def gps(s, res=set()):
if s:
elem = s.pop()
gps(s, res)
res.add(elem)
gps(s, res)
s.append(elem)
res.remove(elem)
else:
print(res)

在阅读了另一个Stack Overflow答案后，我修改了我的函数以使用yield from，但下面修改的代码仍然给了我不正确的结果：

def gps(s, res=set()):
if s:
elem = s.pop()
yield from gps(s, res)
res.add(elem)
yield from gps(s, res)
s.append(elem)
res.remove(elem)
else:
yield res

我的方法哪里出了问题？如有任何提示和澄清，我们将不胜感激。

Answer 1

也许您可以在不使用任何内置方法的情况下尝试此代码。

def subset(nums):
ans = [[]]
for n in nums:
ans += [a+[n] for a in ans]
return ans

nums = [1, 2, 3]
print(subset([1,2,3]))  # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 

或者您仍然更喜欢生成器版本：

def powerset(nums):
"""
This is a generator version
"""
if len(nums) <= 1:
yield nums
yield []
else:
for x in powerset(nums[1:]):
yield [nums[0]]+ x
yield x

if __name__ == '__main__':
nums = [1, 2, 3]
print(list(powerset(nums)))

Answer 2

itertools.combinations可用于获取列表中特定长度的所有元素组合。要获得功率集，您可以将长度为0的所有组合与长度为1的所有组合组合组合，依此类推，直到列表的长度

import itertools
s = [1, 2]
result = []
for x in range(len(s) + 1): 
result.extend(map(set, itertools.combinations(s, r=x)))
print(result)  # [set(), {1}, {2}, {1, 2}]

原始输入实际上应该是一个集合，或者至少具有唯一的值，如果列表具有重复项，则这可能不起作用，因为输入不是"唯一"；设置"；

Answer 3

对于递归方法，正如问题的标题所示，您可以让函数取出输入序列的第一项，然后从序列其余部分的幂集中递归生成每个子集，添加或不添加第一项：

def powerset(seq):
if seq:
first, *rest = seq
for subset in powerset(rest):
yield subset
yield {first, *subset}
else:
yield set()

使得CCD_ 11返回：

[set(), {1}, {2}, {1, 2}]

并且CCD_ 12返回：

[set(), {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}]

由于上述代码中first, *rest = seq中解包的时间复杂度(或切片，在@DanielHao的答案中为nums[1:]的情况下(为O(n(，因此您可以通过首先从输入序列创建迭代器来将步骤的时间复杂程度提高到O(1(

def powerset(seq):
def _powerset(seq):
try:
first = next(seq)
for subset in _powerset(seq):
yield subset
yield {first, *subset}
except StopIteration:
yield set()
yield from _powerset(iter(seq))