我不能理解Python中递归函数的"yield“

Question

我正在试着理解“让步”。

首先，我不能理解的代码如下。

def permutations(seq):
    if len(seq) <= 1: yield seq
    else:
        for perm in permutations(seq[1:]):
            for i in range(len(perm)+1):
                yield perm[i:] + seq[0:1] + perm[:i]

print list(permutations(['police', 'buffalo', 'fish']))

结果如下：

[['fish', 'buffalo', 'police'], ['buffalo', 'police', 'fish'], ['police', 'fish', 'buffalo'], ['buffalo', 'fish', 'police'], ['fish', 'police', 'buffalo'], ['police', 'buffalo', 'fish']]

我对"yield“的理解是它只是用于生成器。我可以理解下面的代码。

def reverse(data):
    for index in range(len(data) -1, -1, -1):
        yield data[index]

for char in reverse('golf'):
    print(char)

f
l
o
g

我的水平就是以上的理解..但是对于递归，我不能理解...请解释一下。谢谢

Answer 1

是的，收益是针对发电机的。这意味着当被调用时，它们会返回迭代器。生成器可以是递归的:它们会调用自己，获得一个迭代器并在其上迭代，在每次迭代中，它们可以根据自己的喜好产生任意多或少的元素。

在您的示例中，permutations是一个生成器，它总是返回一个遍历列表的迭代器。

if len(seq) <= 1: yield seq

非常简单:在简单的情况下，只需生成一个列表，即seq本身。

for perm in permutations(seq[1:]):
        ...

意思是“现在迭代不同的列表序列”，在本例中是第一个元素之后的所有元素排列的序列。在每次迭代中，我们都有一个嵌套循环，该循环将第一个元素插入到排列的每个位置并产生结果。

我希望这能有所帮助。这对我来说有点难，因为我不知道你到底在困惑什么。

更新：操作员想知道为什么第一个结果是逆序的。考虑下面这行：

yield perm[i:] + seq[0:1] + perm[:i]

对于第一个结果(i=0)，这等同于yield perm + seq[0:1] --第一个元素被发送到产生的列表的末尾。通过归纳，这一结果与seq相反。如果您希望第一个结果为['police', 'buffalo', 'fish']，那么您可以这样做：

yield perm[:i] + seq[0:1] + perm[i:]

Answer 2

你给出的代码是根据这个算法工作的：

如果序列只有一项或为空，则根据相同的算法，唯一的排列是将序列itself

• Separate成其第一个元素的序列，以及其所有剩余元素的列表elements

• Consider序列其余部分的所有排列。对于每个排列:对排列中的每个位置：

1. ：
   1. 在该位置分割排列，该分割中原始序列的第一个元素。这是原始sequence.

的新排列

​

​

1. Done.

原始代码在如何实现3.1.2这一点上有点奇怪。我们可以通过使用更多的变量来更清楚地显示与算法的关系，从而使这一点更清晰-这假设您使用的是Python 3：

def permutations(seq):
    if len(seq) <= 1: 
        yield seq 
    else:
        first, *rest = seq
        for perm in permutations(rest):
            for i in range(len(perm)+1):
                before = perm[:i]
                after = perm[i:]
                yield after + [first] + before

正如您所看到的，最后一行无缘无故地切换了排列的开始和结束。它也可以很容易地实现before + [first] + after，但是作者决定不这么做。这不会影响算法的工作方式-它会找到所有的排序，包括镜像的排序-但这意味着它产生它们的顺序可能有点奇怪。

您也可以使用类似的递归生成器来实现reverse。在这种情况下，算法是：

如果序列只有一项或为空，它将自己的reverse

• Split序列转换成它的第一个元素和所有剩余元素的列表

• 使用此算法来反转剩余的每一项最后一步的结果

• 产生原始序列的第一个元素

在Python中，它看起来像这样：

def reverse( seq )：if len(seq) <= 1:返回seq

  first, *rest = seq
  for item in reverse(rest):
       yield item
  # Or you could use:
  #  yield from reverse(rest)
  # Instead of the above loop
  yield first