组合递归算法

Question

我需要用Python编写一个递归函数来计算长度"n“的所有可能组合，而不需要导入类似itertools等的任何内容。

因此，到目前为止，我得到的是：

if n == 0:
    return [[]]
elif lst == []:
    return []
else:
    rest = subsets(lst[1:], n-1)
    for next in lst:  # Loop through something?
        return lst[0] + rest #Add something?

我似乎对递归调用的工作方式缺乏理解，有人能给我解释一下吗？

Answer 1

在没有所需的输出规范的情况下，我们可以编写如下伪代码：

def combinations(sub, data_set, items_needed):
    if you dont need, return sub
    for item in data_set:
        append item to sub
        #pop() item from data_set?
        decrease items_needed # added one more, so we need one less
        combinations(new_sub, data_set, items_needed)

在哪里，poping()或not将取决于您是否需要(或不)子集中的唯一项。

如果您不希望同时使用a、b和b，则还必须跟踪最后添加的项的索引，以便只添加新项以创建新的组合。

def combinations(sub, data_set, index, still_needed):
    if you dont need any, return
    for i in range(index, len(data_set)):
        append data_set[i] to sub
        decrease still_needed
        combinations(sub, data_set, index+1, still_needed)

Answer 2

这听起来像家庭作业问题，听起来很危险。为什么它必须是递归的，因为这看起来很糟糕。

无论如何，您要做的是递归地遍历列表中的每个元素，然后将其附加到长度为n- 1的所有其他组合的开头。因此，如果您的列表是1、2、3，则需要一个算法，其中调用堆栈看起来如下：

foo([], [1, 2, 3], n) ==
  foo([1], [2, 3], n - 1) +
  foo([2], [1, 3], n - 1) +
  foo([3], [1, 2], n - 1)

哪里,

foo([1], [2, 3], n - 1) ==
  foo([1, 2], [3], n - 2) +
  foo([1, 3], [2], n - 2)

等等。

只要有n个== 0，或者中间列表为空，就可以终止递归调用。你只需返回第一个论点。

这一切都有道理吗？(如果需要的话，我可以把它编码。我认为，如果您查看所需的callstacks，它基本上应该将自己放在一起。)

Answer 3

面对这样一个基本问题(一个经常被用作入门级作业或一些编程面试的问题)，一个有用的技巧就是看看RosetteCode (你也可以从这个问题中学习用“口裂”这样的词来打动你的朋友。)特别是这一次，我们发现：

#/usr/bin/env python
# From: http://rosettacode.org/wiki/Combinations#Python
def comb(m, lst):
if m == 0:
    return [[]]
else:
    return [[x] + suffix for i, x in enumerate(lst)
            for suffix in comb(m - 1, lst[i + 1:])]

..。以及其他几十种语言的实现进行比较。

另一个方便的站点是PLEAC (用于“编程语言示例类似于Cookbook”项目) ..。尽管它的学术水平较低，而且倾向于更实际的编程任务。