组合递归算法 [英] Combinations Recursive Algorithm

问题描述

在Python中，我需要编写一个递归函数来计算列表中所有长度 n的可能组合，而无需导入 itertools 等之类的东西。

所以我到目前为止是：

 如果n == 0 ：
 return [[]] 
 elif lst == []：
 return [] 
 else：
 rest = subsets（lst [1：]，n- 1）
首先进入下一个：＃遍历某些内容？ 
 return lst [0] + rest＃添加一些内容？ 
  

我似乎对递归调用的工作方式缺乏了解，有人可以向我解释一下吗？

解决方案

在缺少必需的输出规范的情况下，我们可以编写一些伪代码，如下所示：

  def组合（sub，data_set，items_needed）：
如果您不需要，则为data_set中的项目返回sub 
：
将项目追加到data_set的子
 #pop（）项目中？ 
减少items_needed＃再增加一个，因此我们需要少一个
组合（new_sub，data_set，items_needed）
  

poping（）与否（取决于是否需要子集中的唯一项）。

如果您说不想要[a，b]和[b，a]都需要跟踪最后添加的项的索引，以便仅添加新项以创建新组合。

  def组合（子，数据集，索引，still_needed）：
如果不需要，返回范围内的i的
（index，len （data_set））：
将data_set [i]追加到sub 
减少still_needed 
组合（sub，data_set，index + 1，still_needed）
  

I need to write a recursive function that calculates all the possible combinations of length "n" in a list, in Python, without importing anything like itertools etc.

So what I have so far is:

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?

I seem to be lacking an understanding of how the recursive calls work, can someone explain this to me?

解决方案

In the absence of the required output specifications, we could write some pseudo-code like this:

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)

Where poping() or not will depend on you wanting (or not) unique items in the subset.

If you say you don't want both [a, b] and [b, a] you would have to also keep track of the index of the last item added, in order to only add new items to create new combinations.

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)

这篇关于组合递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！