python递归列表组合而不使用生成器 [英] python recursion list combinations without using generator
问题描述
我正在学习python3.为了更多地考虑递归,我想实现一个函数comb(n,k),该函数返回一个列表,其中包含集合{1,2,…,n}中kk元素的所有组合.
I am learning python3. To think more about recursion, I want to implement a function comb(n, k) that returns a list consisting of all the combinations of kk elements out of a set {1,2,…,n}.
我认为使用循环是不明智的,因为嵌套循环的数量取决于k.因此,我以递归的方式考虑它.我尝试编写受此问题启发的函数虽然我找不到正确的答案.
I think it's not wise to use the loop since the number of the nested loop depends on k. So I consider it with recursion. I try to write the function inspired by This question while I can't get the right answer.
def combinations(sub, data_set, index, still_needed):
if still_needed == 0:
return sub
for i in range(index, len(data_set)):
sub.append(data_set[i])
still_needed = still_needed - 1
return combinations(sub, data_set, index+1, still_needed)
def comb(n, k):
data_set = list(range(1, n+1))
print (combinations([], data_set, 0, k))
如果我测试Comb(6,3),我只会得到[1,2,3].我想获得所有组合.我的代码有什么问题?还是错过了重要的事情?我只想学习python的递归,这不是一项家庭作业,谢谢.
If I test Comb(6,3), I only get [1,2,3]. I want to get all combinations. What's the problem in my code? or something important missed? I just want to learn the recursion of python and it is not a homework, thanks.
预期结果如下:
[[1, 5, 6],
[2, 5, 6],
[3, 5, 6],
[4, 5, 6],
[1, 4, 6],
[2, 4, 6],
[3, 4, 6],
[1, 3, 6],
[2, 3, 6],
[1, 2, 6],
[1, 4, 5],
[2, 4, 5],
[3, 4, 5],
[1, 3, 5],
[2, 3, 5],
[1, 2, 5],
[1, 3, 4],
[2, 3, 4],
[1, 2, 4],
[1, 2, 3]]
虽然顺序并不重要.我将很感激,如果有任何pythonic的方法来解决这个问题,例如.嵌套的 [可迭代的项目表达式]
(因为我尝试过但失败了).
While the order is not important. And I will appreciate that if there is any pythonic way to solve this question eg. nested [expression for item in iterable]
(since I have tried it but failed).
再次感谢.
推荐答案
函数中的问题是,在 for
循环中有一个 return
语句:它将停止在第一次迭代中执行该功能.
The problem in your function is that you have a return
statement inside your for
loop: it stops execution of the function during the first iteration.
这是您可以用于递归的基本结构:
Here's the basic structure you could use for recursion:
def combinations(n, k, min_n=0, accumulator=None):
if accumulator is None:
accumulator = []
if k == 0:
return [accumulator]
else:
return [l for x in range(min_n, n)
for l in combinations(n, k - 1, x + 1, accumulator + [x + 1])]
print(combinations(6, 3))
# [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 6], [1, 3, 4], [1, 3, 5], [1, 3, 6], [1, 4, 5], [1, 4, 6], [1, 5, 6], [2, 3, 4], [2, 3, 5], [2, 3, 6], [2, 4, 5], [2, 4, 6], [2, 5, 6], [3, 4, 5], [3, 4, 6], [3, 5, 6], [4, 5, 6]]
要检查结果是否正确,可以针对 itertools
进行测试:
To check if the result's correct, you can test it against itertools
:
import itertools
print(list(itertools.combinations(range(1,7),3)))
# [(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 4), (1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (1, 5, 6), (2, 3, 4), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6), (2, 5, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), (4, 5, 6)]
print(
list(itertools.combinations(range(1, 7), 3))
==
[tuple(comb) for comb in combinations(6, 3)]
)
# True
这篇关于python递归列表组合而不使用生成器的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!