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 ]时，它会将原始列表的最后一个元素附加到其中，而不是发送到递归方法中的较小的列表。有没有办法解决这个问题？

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

- Metatrix

---

预期的答案是什么？这似乎是你正在寻找的。显然，这种方法在过程中积累了很多重复项。 - Cocksure

你想要将[list(itertools.permutations(li[:x])) for x in range(len(li))]这样的内容放在一维列表中吗？ - Dica

@Cocksure 我错了，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 - Metatrix

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

- Miguel de Matos

---

我希望结果按字典顺序排序？ - Nidhi

@Nidhi 你可能会注意到这个解决方案按照逆字典序对结果进行排序。只需排列返回值即可获得字典序：return [[l[0]] + y for y in x] + x。 - Stef

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

- Pi Marillion

---

这基本上与在itertools模块页面给出的powerset的方法相同——但他们的版本实际上返回一个迭代器，对于可能产生巨大结果的情况来说，这要比列表更好。 - DaoWen

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

- Metatrix

---

它缺少空集（'[]'）。 - rmk

Answer 4

改进@Miguel Matos的答案

def subsets(set_inp):
    if set_inp == []:
        return [[]]
    x = subsets(set_inp[1:])

    return sorted( x + [[set_inp[0]] + y for y in x])
print(subsets([1,2,3]))

- SHARON KANINI

Answer 5

继续 @Miguel 和 @Abdul 提供的答案...以下函数确保按字典顺序输出。

def subset(A):
    if A == []:
        return [[]]
    sub = subset(A[:-1])
    return sub + [rem + [A[-1]] for rem in sub] 

tests = [[], [1], [1,2], [1,2,3]]
for test in tests:
    print(subset(test))

RESULT

[[]]
[[], [1]]
[[], [1], [2], [1, 2]]
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

- Semeriuss

Answer 6

您可以使用Lambda函数和 map 来避免使用列表推导或for循环。

在Python中，我认为这是一个正确的“功能性”幂集函数：

def powerSet(input):


# at tree leaf, return leaf
if len(input)==0:
    return [[]];

# if not at a leaf, trim and recurse
# recursion is illustrated as follows:
# e.g. S = {1,2,3}
# S_trim = S without first element:
# {(),(2),(3),(2,3)}
# S_trim concatenated with first element:
# {(1),(1,2),(1,3),(1,2,3)}
# we keep the character sliced from front and concat it 
# with result of recursion

# use map to apply concatenation to all output from powerset

leading = (input[0])
new_input = input[1:len(input)]


ps1 = list((powerSet(new_input)))
# concatenate over powerset-ed set
ps2 = map(lambda x: [leading]+x,ps1) 

ps_list = list(map(lambda x: list(x),ps2))

return ps1+ ps_list    

- Phil

Answer 7

使用 @Miguel Matos 的想法，我们可以按字典顺序获取这些内容，方法如下：

def foo(l, p = [], d = {}):
    if len(l)==0: 
        return [[]]
    
    x = foo(l[:-1])
    
    return x+ [[l[-1]] + y for y in x]

返回： [[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1], [4], [4, 1], [4, 2], [4, 2, 1], [4, 3], [4, 3, 1], [4, 3, 2], [4, 3, 2, 1]]

- Abdul