python通过递归函数获取所有子集

Question

我编写了一些 python 代码来通过递归获取所有子集。

如果给定一个数据

data = [1,2,3,4,5]
length = 3

结果将以 3 长度打印所有子集像这样

1,2,3
1,2,4
1,2,5
2,3,4
2,3,5...

这是我的代码

data = [1,2,3,4,5]
n = 5
r = 3 
    templist = []
    def re(max,length,idx):
        if idx == max:
            return
        if idx == length:
            for i in templist:
                print(" "+str(i))
            print("\n")
            return
        else:
            templist.append(data[idx])
            re(max,length,idx+1)
            templist.pop()
            re(max,length,idx+1)
    if __name__ == "__main__":
     re(n,r,0)

我的期望是循环所有可能的子集但是当它遇到调用时它会失败 re(max,length,idx+1) 后 temlist.pop()

当代码进入第二个re()函数时我希望它附加 templist.append(data[4]) 因为第一个 re() 函数 return 通过 if 条件 if idx == length:

当idx为3时，idx与length(3)相同。所以递归结束，运行 temlist.pop() 和会进入第二个re(4)函数因为我编码 idx+1

但它会失败 idx只圈在2~3之间

所以我改了第二个递归函数

re(max,length,idx+1)

至

re(max,length,idx+2)

我彻底崩溃了。

我认为我的逻辑基本是错误的。但我不知道在哪里修复它我该如何解决以按预期调用递归？

Answer 1

方法如下：

def func(data, length, lst=[]):
    for i in data[length - 1:]:
        lst.append(data[:length - 1] + [i])
    if data:
        func(data[1:], length, lst)
    return lst

data = [1,2,3,4,5]
length = 3

print(func(data, length))

输出：

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [2, 3, 4], [2, 3, 5], [3, 4, 5]]

解释：

定义一个接受三个参数的函数，列表(data)，长度(length) 和一个空列表 (lst) 来存储输出值 （在函数外定义它被认为是不好的做法） .
遍历 data 列表中第一个 length - 1 索引元素之外的元素，并将 0 索引中的元素附加到 length - 1 索引加上迭代的当前元素。
如果 data 列表没有变空，再次调用当前函数，但使用切片 [1:] 删除第一个字符。
如果 data 列表没有变空，return lst 列表。

您的另一个选择是使用 Python 强大的生成器。使用这种技术，我们不再需要 lst 参数 -

def func(data, length):
    for i in data[length - 1:]:
        yield data[:length - 1] + [i]
    if data:
        yield from func(data[1:], length)

现在我们可以使用迭代检索排列 -

data = [1,2,3,4,5]
length = 3

for perm in func(data, length):
  print(perm)

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[2, 3, 4]
[2, 3, 5]
[3, 4, 5]

或者我们可以在 list -

中收集所有排列

data = [1,2,3,4,5]
length = 3

print(list(func(data, length)))

[[1, 2, 3], [1, 2, 4], [1, 2, 5], [2, 3, 4], [2, 3, 5], [3, 4, 5]]

Answer 2

最好的方法是使用 itertools 的内置排列。

from itertools import permutations
data = [1,2,3,4,5]
length = 3
res = list(permutations(data, length))

python通过递归函数获取所有子集

python get all subset by recursive function

python

algorithm

recursion

subset

tail-recursion