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()函数通过if条件返回 if idx == length:

当idx为3时，idx与长度（3）相同。 因此，递归结束时，运行temlist.pop()并 它将进入第二个re(4)函数 因为我编码了idx+1

但它将失败 idx只能在2~3之间循环

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

re(max,length,idx+1)

到

re(max,length,idx+2)

我完全崩溃了

我认为我的逻辑基本上是错误的。 但我不知道在哪里修复它，我如何解决调用递归的问题

Answer 1

最好的方法是使用itertools中的内置置换

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

Answer 2

以下是如何：

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

说明：

1. 定义一个包含三个参数的函数，list（data）、length（length）和一个空的list（lst）来存储输出值（在函数之外定义它被认为是不好的做法）

2. 除了第一个length - 1索引元素之外，还遍历data列表的元素，并将0索引中的元素附加到length - 1索引和迭代的当前元素

3. 如果data列表没有变为空，请再次调用当前函数，但使用切片[1:]删除第一个字符

4. 如果data列表没有变为空，则返回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]]