时间戳

首页 > 解决方案 > 在列表中获取所有递归结果

python - 在列表中获取所有递归结果

问题描述

我正在学习python递归。为了练习，我正在给一个任务来查找列表的所有子集。例如函数：

subset([1,2)] should return [[1,2],[1],[2],[]]

我可以在递归的帮助下让我的函数打印这些结果

def subset(List):
   print(List)
   n = len(List)
   if n > 2:
      for i in range(n):
         subset(List[:i]+List[i+1:])

   if n == 2:
      subset([List[0]])
      subset([List[1]])
   if n == 1:
      subset([])
pass

L = [1,2]
test = subset(L)

打印语句打印：

[1, 2], [1], [], [2], []

我希望拥有不打印的功能，而是将其返回到所需结果给出的列表中。

我会喜欢你对此的看法。

标签： pythonlistrecursion

解决方案

首先，如果您实际上不必自己实现它，标准库很乐意为您提供帮助。

但这是研究递归的一个有趣的问题，所以让我们仔细看看。

与此处类似，对于递归的复杂用途，a）一次进行多个递归调用，b）需要以某种方式“累积”结果，我的建议是编写一个递归生成器。您可以机械地转换它：

  • 替换print为yield

  • yield from递归调用（正如我在另一个答案中指出的那样，对于不需要累积结果的情况，您通常会想要return这些）。

然后从递归之外，您可以将结果收集到 alist中，或直接迭代它们。

但是，您的算法也存在一个问题：缺少两个或多个原始元素的结果将出现不止一次（正如您已经看到的），因为它们的递归“路径”不止一个。您想要的算法是：

  • 递归获取不包含第一个元素的子集
  • 对于其中的每一个，发出两个结果：一个带有前置第一个元素，一个没有前置

所以yield from我们不会迭代结果，做一些修改，然后yield在那个循环中。

把所有这些放在一起，它看起来像：

def power_set(items):
    if not items: # empty set; base case for recursion.
        yield items
        return
    # Pull off the first element,
    first, *rest = items
    # then iterate over the recursive results on the rest of the elements.
    for without_first in power_set(rest):
        yield [first] + without_first
        yield without_first

# let's test it:
list(power_set([1,2,3]))
# [[1, 2, 3], [2, 3], [1, 3], [3], [1, 2], [2], [1], []]
# Good, just what we want - with no duplicates.

推荐阅读