递归函数，返回从列表中选择的大小为n的组合

Question

我正在尝试编写一个递归函数，它将整数n和列表l作为其输入，并返回可以从l中的元素中选择的所有大小为n的组合的列表。我知道我可以使用itertools，但我想要更好地编写递归函数，我相信编写自己的函数会对我有所帮助。

例如，如果你输入：

n = 3

l = [1, 2, 3, 4]

我希望输出为：

`[ [1, 2, 3], [1, 3, 4], [2, 3, 4], [1, 2, 4] ]

到目前为止，我已经编写了这段代码：

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

我发现this example of such a function for permutations很有帮助，但我很难实现类似的东西。

为了澄清，我按照我的方式设置我的基本情况，因为我期望在递归调用中传递sliced_list和m，如果你想象i = 3的情况，你将有sliced_list和m的空列表当你已经足够深入建立一个组合时，它将是1。但我没有和这些基本情况结婚。

让我试着总结一下我的问题：

1. 如何生成一个完全是列表列表的最终结果，而不是列表列表列表...（depth = n）？
2. 我的递归调用应该是什么样的？
3. 我是以错误的方式解决这个问题吗？

Answer 1

首先，我建议您将功能布局为：

def get_combinations(array, n):
    solutions = []

    # all the code goes here

    return solutions

这样，如果有一个问题的情况，比如n == 0，你可以忽略它并得到一个有效的（空的）结果。下一个问题是这一行错了：

elif n == 1:
    return [array[0]]

如果n == 1要返回一个数组，并且数组的每个元素都包含在list中，那么这是正确的做法：

if n == 1:
    solutions = [[element] for element in array]

这是你的基本情况，因为递归中的下一层将构建在此基础上。接下来是问题的核心。如果n > 1和数组有内容，那么我们需要循环遍历数组的索引。对于每一个，我们将在当前索引和n - 1之后递归调用自己：

sub_solutions = get_combinations(array[index + 1:], n - 1)

这返回部分解决方案。我们需要将元素填充到当前索引，即。 array[index]，在sub_solution的每个sub_solutions的前面，并将每个增强的sub_solution添加到我们在函数末尾返回的solutions列表中：

solutions.append([array[index]] + sub_solution)

就是这样！