递归函数，返回从列表中选择的大小为n的组合 [英] Recursive function that returns combinations of size n chosen from list
问题描述
我正在尝试编写一个递归函数，该函数将一个整数 n 和一个列表 l 作为其输入，并返回大小为n的所有组合的列表可以从 l 中的元素中选择.我知道我可以使用itertools，但是我想变得更好地编写递归函数，并且我相信编写自己的函数将对我有所帮助.
I am trying to write a recursive function which takes as its inputs an integer n, and a list l, and returns a list of all the combinations of size n that can be chosen from the elements in l. I'm aware that I can just use itertools, but I want to become better at writing recursive functions, and I believe writing my own function will help me.
例如，如果您输入:
n = 3
l = [1、2、3、4]
我希望输出为:
`[[1、2、3]，[1、3、4]，[2、3、4]，[1、2、4]]
`[ [1, 2, 3], [1, 3, 4], [2, 3, 4], [1, 2, 4] ]
到目前为止，我已经编写了以下代码:
So far I've written this code:
def get_combinations(l, n): # returns the possible combinations of size n from a list of chars
if len(l) == 0:
return []
elif n == 1:
return [l[0]]
newList = list()
for i in range(len(l)):
sliced_list = l[i:]
m = n - 1
#lost here, believe I need to make a recursive call somewhere with get_combinations(sliced_list, m)
return newList
我发现此类示例排列功能很有帮助，但是我正在努力实现类似的功能.
I found this example of such a function for permutations helpful, but I'm struggling to implement something similar.
为了澄清起见，我以我的方式设置了基本案例，因为我希望在我的递归调用中传递 sliced_list 和 m ，如果你想像的话在 i = 3 的情况下，您将有一个 sliced_list 的空列表，而当您深入时， m 将为1建立一个组合.但是我还没有嫁给这些基本案例.
To clarify, I set up my base cases in the way I did because I'm expecting to pass sliced_list and m in my recursive call, and if you imagine the situation when i = 3, you'll have an empty list for sliced_list, and m will be 1 when you've gone deep enough to build up a combination. But I'm not married to these base cases.
让我尝试总结一下我的问题:
Let me try to summarize the questions I have:
-
如何生成最终结果，该结果恰好是列表列表，而不是列表列表...(深度= n)?
How do I produce a final result which is exactly a list of lists, instead of a list of lists of lists of lists ... (depth = n)?
我的递归调用应该是什么样的?
What should my recursive call look like?
我要用完全错误的方式解决这个问题吗?
Am I going about this problem in exactly the wrong way?
推荐答案
首先，我建议您对函数进行布局，例如:
First I would recommend that you layout your function like:
def get_combinations(array, n):
solutions = []
# all the code goes here
return solutions
这样，如果出现问题，例如 n == 0 ，您可以忽略它并获得有效的(空)结果.下一个问题是此行是错误的:
That way if there's a case that's a problem, like n == 0, you can just ignore it and get a valid (empty) result. The next issue is this line is wrong:
elif n == 1:
return [array[0]]
如果 n == 1 的正确方法是返回一个数组，该数组的 every 元素包装在 list 中:
The correct thing to do if n == 1 is to return an array with every element of the array wrapped in a list:
if n == 1:
solutions = [[element] for element in array]
这是您的基本情况，因为递归的下一层将基于此.接下来是问题的核心.如果 n>1 并且数组具有内容，那么我们需要遍历数组的索引.对于每个索引，我们将递归地调用当前索引和 n-1 :
This is your base case as the next layer up in the recursion will build on this. What comes next is the heart of the problem. If n > 1 and the array has content, then we need to loop over the indexes of the array. For each we'll call ourself recursively on everything past the current index and n - 1:
sub_solutions = get_combinations(array[index + 1:], n - 1)
这将返回 partial 解决方案.我们需要将元素 at 填充到当前索引中，即. array [index] ，放在 sub_solutions 中每个 sub_solution 的前面，然后将每个扩展的 sub_solution 添加到我们的列表中我们在函数末尾返回的 solutions :
This returns partial solutions. We need to stuff the element at the current index, ie. array[index], onto the front of each sub_solution in sub_solutions, and add each augmented sub_solution to our list of solutions that we return at the end of the function:
solutions.append([array[index]] + sub_solution)
就是这样！
这篇关于递归函数，返回从列表中选择的大小为n的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
