returns 从列表中选择大小 n 的组合的递归函数

Question

我正在尝试编写一个递归函数，它将一个整数 n 和一个列表 l 以及大小为 n 的所有组合的列表 returns 作为其输入可以从 l 中的元素中选择。我知道我可以只使用 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。但我没有嫁给这些基本案例。

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

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

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 正确的做法是 return 一个数组，数组的每个元素包裹在 list 中：

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

这是您的基本情况，因为递归中的下一层将以此为基础。接下来是问题的核心。如果 n > 1 并且数组有内容，那么我们需要遍历数组的索引。对于每个我们将递归地调用自己超过当前索引和 n - 1:

的所有内容

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

这returns 部分解决方案。我们需要将元素 填充到 当前索引，即。 array[index]，到 sub_solutions 中每个 sub_solution 的前面，并将每个扩充的 sub_solution 添加到我们 return 的 solutions 列表中函数结束：

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

就是这样！

returns 从列表中选择大小 n 的组合的递归函数

Recursive function that returns combinations of size n chosen from list

python

recursion

combinatorics