python - 解释列出所有排列的 Python 代码

Question

class Permutation:
    def __init__(self,justalist):
        self._data = justalist[:]
        self._sofar = []
    def __iter__(self):
        return self.next()
    def next(self):
        for elem in self._data:
            if elem not in self._sofar:
                self._sofar.append(elem)
                if len(self._sofar) == len(self._data):
                    yield self._sofar[:]
                else:
                    for v in self.next():
                        yield v
                self._sofar.pop()

在网上找到了这段代码（http://users.softlab.ntua.gr/~ttsiod/yield.html）。试图弄清楚，但没有取得太大进展。真正让我绊倒的部分是：

                 for v in self.next():
                    yield v
                 self._sofar.pop()

通过执行以下操作运行该类的代码：

      for i in Permutation(a):
         print(i)

我读过这个：

“通过调用yield，下一个成员现在是一个生成器函数，所以我们不能只是简单地再次调用next——如果我们这样做了，我们将丢失返回的生成器对象，因此，返回的排列！我们必须改为循环在 self.next() 中使用简单的 for v 返回结果：yield v。这样，结果会正确传播到“父”调用。

我不知道这是否能解释发生了什么，但这对我来说毫无意义。（我以为我了解生成器。）

Answer 1

这个类是一个递归调用自身（self.next()）的生成器。

这有点奇怪，因为当您向生成器询问其所有值时，它并没有像您期望的那样通过返回self（具有函数的对象）来真正遵循迭代协议。.next()相反，它返回 的结果self.next()，这是相当糟糕的措辞。该next函数应该只是被调用permutations()，因为该函数实际上与迭代协议中需要next一个函数这一事实没有任何关系。next

无论如何，如果您使用递归深度参数扩充函数，您可以看到它的递归跟踪：

class Permutation:
    def __init__(self,justalist):
        self._data = justalist[:]
        self._sofar = []
    def __iter__(self):
        return self.next()
    def next(self, depth=0):
        debug = lambda text:print('\t'*depth+' '+text)
        for elem in self._data:
            #print( 'self._data: {}'.format(self._data) )
            #print( 'self._sofar: {}'.format(self._sofar) )
            if elem not in self._sofar:
                self._sofar.append(elem)
                if len(self._sofar) == len(self._data):
                    debug( 'yielding self._sofar[:]: {}'.format(self._sofar[:]) )
                    yield self._sofar[:]
                else:
                    for v in self.next(depth+1):
                        debug( 'yielding elements of self.next() one-by-one: {}'.format(v) )
                        yield v
                self._sofar.pop()

演示：

>>> list( Permutation(range(4)) )
                         yielding self._sofar[:]: [0, 1, 2, 3]
                 yielding elements of self.next() one-by-one: [0, 1, 2, 3]
         yielding elements of self.next() one-by-one: [0, 1, 2, 3]
 yielding elements of self.next() one-by-one: [0, 1, 2, 3]
                         yielding self._sofar[:]: [0, 1, 3, 2]
                 yielding elements of self.next() one-by-one: [0, 1, 3, 2]
         yielding elements of self.next() one-by-one: [0, 1, 3, 2]
 yielding elements of self.next() one-by-one: [0, 1, 3, 2]
                         yielding self._sofar[:]: [0, 2, 1, 3]
                 yielding elements of self.next() one-by-one: [0, 2, 1, 3]
         yielding elements of self.next() one-by-one: [0, 2, 1, 3]
 yielding elements of self.next() one-by-one: [0, 2, 1, 3]
                         yielding self._sofar[:]: [0, 2, 3, 1]
                 yielding elements of self.next() one-by-one: [0, 2, 3, 1]
         yielding elements of self.next() one-by-one: [0, 2, 3, 1]
 yielding elements of self.next() one-by-one: [0, 2, 3, 1]
                         yielding self._sofar[:]: [0, 3, 1, 2]
                 yielding elements of self.next() one-by-one: [0, 3, 1, 2]
         yielding elements of self.next() one-by-one: [0, 3, 1, 2]
 yielding elements of self.next() one-by-one: [0, 3, 1, 2]
                         yielding self._sofar[:]: [0, 3, 2, 1]
                 yielding elements of self.next() one-by-one: [0, 3, 2, 1]
         yielding elements of self.next() one-by-one: [0, 3, 2, 1]
 yielding elements of self.next() one-by-one: [0, 3, 2, 1]
                         yielding self._sofar[:]: [1, 0, 2, 3]
                 yielding elements of self.next() one-by-one: [1, 0, 2, 3]
         yielding elements of self.next() one-by-one: [1, 0, 2, 3]
 yielding elements of self.next() one-by-one: [1, 0, 2, 3]

如您所见，数据流如下：递归进行到最深的级别（在本例中为 4，len([0,1,2,3])即 4），产生一个排列，并将其返回到前一个级别。该级别将其返回到之前的级别，依此类推。在最高级别，收益率将其返回。

总之，这是一个破碎而糟糕的实现，因为：

1. 它可以通过带有这个额外的类废话的递归函数模式来完成
2. 它next()以一种强烈暗示某事的方式定义，但实际上做了其他事情。
3. 如果任何值重复，它将失败，例如Permutation([0,1,1])将失败

你应该只使用http://docs.python.org/library/itertools.html#itertools.permutations ( from itertools import permutations)

Answer 2

关键思想是产生以开头Permutation.next()的项目的所有排列。_data_sofar

为此，我们尝试将每个可能的元素添加到_sofar. 然后有两种情况：一种_sofar是足够长的（即，我们有一个完整的排列），在这种情况下，我们只产生它的一个副本；或者它不是（即，我们有一个部分排列），在这种情况下我们递归调用next- 通常会产生很多排列，所以我们必须自己一个一个地产生它们。

顺便说一句，我认为如果代码更像这样（危险：未经测试的代码），代码会更简洁，更容易理解：

def next(self):
    if len(self._sofar) == len(self._data):
        yield self._sofar[:]
    else:
        for elem in self._data:
            if elem not in self._sofar:
                self._sofar.append(elem)
                for v in self.next():
                    yield v
                self._sofar.pop()

which also has the merit of giving the right answer when there are no elements (there's exactly one permutation, the empty sequence; the code as given yields none). There are a few optimizations I'd be inclined to make, too, but they aren't important.