组合递归算法

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()是否将取决于您想要(或不)子集中的唯一项。

如果你说你不想同时要[a, b]和[b, a]，你还必须跟踪最后添加的项的索引，以便只添加新项来创建新的组合。

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或中间列表为空时，可以终止递归调用。你只返回第一个参数。

这些都有意义吗?(如果需要的话，我可以编写代码。我认为，如果您查看所需的调用栈，它应该主要将自己放在一起。

Answer 3

面对这样一个基本问题(经常用作入门级家庭作业或一些编程面试)时，一个有用的技巧是查看RosetteCode(从中你也可以学会用"chrestomathy"之类的词给你的朋友留下深刻印象)。对于这个，我们发现:

#/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(用于"编程语言示例相似食谱"项目)…虽然它不太学术性，更倾向于更实际的编程任务。