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(): yield v の単純な for v で結果を返しました。このようにして、結果は「親」呼び出しに適切に伝達されます。

これで何が起こっているのかわかりませんが、私には何の意味もありません。(私はジェネレーターを理解していると思っていました。)

Answer 1

このクラスは、自分自身を再帰的に呼び出すジェネレーターです ( self.next())。

ジェネレーターにそのすべての値を要求すると、期待どおりにself(関数を持つオブジェクト) を返すことによって、実際には反復プロトコルに従っていないため、少し奇妙です。.next()むしろ、self.next()非常に不適切な表現である の結果を返します。関数は、反復プロトコルで関数が必要であるという事実とはまったく関係がないため、next単に呼び出されるべきです。permutations()nextnext

とにかく、再帰の深さパラメータで関数を拡張すると、これの再帰トレースを見ることができます:

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]

ご覧のとおり、データの流れは次のとおりです。再帰は最も深いレベル (この場合len([0,1,2,3])は 4、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ます。次に 2 つのケースがあります。どちらか_sofarが十分に長い場合 (つまり、完全な順列が得られた場合)、その場合は、そのコピーを生成するだけです。そうでない場合 (つまり、部分置換がある場合) は、再帰的に呼び出しますnext-- 一般に、多くの順列が生成されるため、それらを 1 つずつ生成する必要があります。

ちなみに、コードは次のようにすれば、よりすっきりと理解しやすくなると思います (危険: テストされていないコード):

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()

これには、要素がない場合に正しい答えを与えるというメリットもあります (順列は 1 つだけで、空のシーケンスがあり、与えられたコードは何も生成しません)。私がやりたいと思う最適化もいくつかありますが、それらは重要ではありません。