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

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

    

我在处理这个问题时哪里做错了？希望能得到一些提示和澄清。

- ben348943

---

这个方法需要递归吗？ - Iain Shelvington

它并不会，但我的第一个想法是编写一个递归解决方案，其中有两个递归子调用：一个生成包含特定元素的所有子集，另一个生成不包含该特定元素的所有子集。 - ben348943

输出顺序重要吗？ - Daniel Hao

@james348943，你的递归方法是正确的。请看我的答案以获取参考实现。 - blhsing

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

- Daniel Hao

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}]

原始输入应该是一个集合，或者至少具有唯一的值，如果列表中有重复项，则可能无法正常工作，因为输入不是“集合”

- Iain Shelvington

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]))才能返回：

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

而 list(powerset([1, 2, 3])) 返回：

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

由于上述代码中 first, *rest = seq 的解包时间复杂度为 O(n)（或者在 @DanielHao 的回答中，nums[1:] 的切片操作），您可以通过从输入序列首先创建一个迭代器，以便在每个递归级别中以常数时间获取序列的下一项，从而将步骤的时间复杂度提高到 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))

- blhsing