在 Python 中使用递归和 Yield 语句生成幂集

Question

我对 Python 有点陌生，正在完成编程练习。我编写了以下递归方法来根据 Python 中的输入列表生成 power set。它应该 return 一个生成器，生成作为 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)

阅读另一篇文章后我修改了我的函数以使用 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

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 2

或许您可以试试这段代码，无需任何内置方法。

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 3

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

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

所以 list(powerset([1, 2])) returns:

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

那 list(powerset([1, 2, 3])) returns:

[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))

在 Python 中使用递归和 Yield 语句生成幂集

Generating Power Set with Recursion and Yield Statement in Python

python

algorithm

recursion

powerset