用于显示给定集的所有子集的Python递归函数

Question

我有以下python函数来打印数字列表的所有子集：

def subs(l):
    if len(l) == 1:
        return [l]
    res = []
    for sub in subs(l[0:-1]):
        res.append(sub)
        res.append([l[-1]])
        res.append(sub+[l[-1]])
    return res

li = [2, 3, 5, 8]
print(subs(li))

这将返回：

[[2], [8], [2, 8], [5], [8], [5, 8], [2, 5], [8], [2, 5, 8], [3], [8], [3, 8], [5], [8], [5, 8], [3, 5], [8], [3, 5, 8], [2, 3], [8], [2, 3, 8], [5], [8], [5, 8], [2, 3, 5], [8], [2, 3, 5, 8]]

这不是我们期望的答案。看起来python通过引用将列表l放入函数中。因此，当我追加l-1时，它会追加原始列表的最后一个元素，而不是发送到递归方法中的较小的列表。有什么办法解决这个问题吗？

可以使用元组来解决这个问题，但是我想知道是否有一个使用列表的解决方案。

Answer 1

def subs(l):
    if l == []:
        return [[]]

    x = subs(l[1:])

    return x + [[l[0]] + y for y in x]

结果：

>>> print (subs([1, 2, 3]))
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Answer 2

有一个方便的Python模块可以帮助：

import itertools
def subs(l):
    res = []
    for i in range(1, len(l) + 1):
        for combo in itertools.combinations(l, i):
            res.append(list(combo))
    return res

研究结果如下：

>>> subs([1,2,3])
[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Answer 3

实际上，按照我最初的想法，通过引用调用Python没有问题。在这种情况下，在所有递归调用中，l-1将为8。但在递归调用中，l-1分别是3、5、8.这个修改后的函数解决了这个问题：

def subs(l):
    if len(l) == 1:
        return [l]
    res = []
    subsets = subs(l[0:-1])
    res = res+subsets
    res.append([l[-1]])
    for sub in subsets:
        res.append(sub+[l[-1]])
    return res

返回：

[[2], [3], [2, 3], [5], [2, 5], [3, 5], [2, 3, 5], [8], [2, 8], [3, 8], [2, 3, 8], [5, 8], [2, 5, 8], [3, 5, 8], [2, 3, 5, 8]]