101

最近、重要な制約を持つ特定のシーケンスを生成する関数を作成しました。問題は自然な再帰的解決策にありました。さて、入力が比較的小さい場合でも、シーケンスは数千であるため、すべてのシーケンスでリストを埋めるために使用するのではなく、ジェネレーターとしてアルゴリズムを使用することをお勧めします。

これが例です。再帰関数を使用して文字列のすべての順列を計算するとします。次の素朴なアルゴリズムは、追加の引数'storage'を取り、それが見つかるたびに順列を追加します。

def getPermutations(string, storage, prefix=""):
   if len(string) == 1:
      storage.append(prefix + string)   # <-----
   else:
      for i in range(len(string)):
         getPermutations(string[:i]+string[i+1:], storage, prefix+string[i])

storage = []
getPermutations("abcd", storage)
for permutation in storage: print permutation

（非効率性については気にしないでください。これは単なる例です。）

ここで、関数をジェネレーターに変換します。つまり、ストレージリストに追加するのではなく、順列を生成します。

def getPermutations(string, prefix=""):
   if len(string) == 1:
      yield prefix + string             # <-----
   else:
      for i in range(len(string)):
         getPermutations(string[:i]+string[i+1:], prefix+string[i])

for permutation in getPermutations("abcd"):
   print permutation

このコードは機能しません（関数は空のジェネレーターのように動作します）。

私は何かが足りないのですか？上記の再帰的アルゴリズムを反復的なものに置き換えることなくジェネレーターに変える方法はありますか？

4

3 に答える 3

118 
def getPermutations(string, prefix=""):
    if len(string) == 1:
        yield prefix + string
    else:
        for i in xrange(len(string)):
            for perm in getPermutations(string[:i] + string[i+1:], prefix+string[i]):
                yield perm

またはアキュムレータなし:

def getPermutations(string):
    if len(string) == 1:
        yield string
    else:
        for i in xrange(len(string)):
            for perm in getPermutations(string[:i] + string[i+1:]):
                yield string[i] + perm
于 2008-10-29T23:53:47.840 に答える
29

これによりlen(string)-deep 再帰が回避され、一般にジェネレーター内のジェネレーターを処理するための優れた方法です。

from types import GeneratorType

def flatten(*stack):
    stack = list(stack)
    while stack:
        try: x = stack[0].next()
        except StopIteration:
            stack.pop(0)
            continue
        if isinstance(x, GeneratorType): stack.insert(0, x)
        else: yield x

def _getPermutations(string, prefix=""):
    if len(string) == 1: yield prefix + string
    else: yield (_getPermutations(string[:i]+string[i+1:], prefix+string[i])
            for i in range(len(string)))

def getPermutations(string): return flatten(_getPermutations(string))

for permutation in getPermutations("abcd"): print permutation

flattenyield別のジェネレーターを反復してyield各項目を手動で ing する代わりに、単純に ing するだけで、別のジェネレーターで進行を続けることができます。

Python 3.3yield fromでは構文が追加され、サブジェネレーターへの自然な委譲が可能になります。

def getPermutations(string, prefix=""):
    if len(string) == 1:
        yield prefix + string
    else:
        for i in range(len(string)):
            yield from getPermutations(string[:i]+string[i+1:], prefix+string[i])
于 2008-10-31T00:05:38.003 に答える
20

getPermutations の内部呼び出し -- これもジェネレーターです。

def getPermutations(string, prefix=""):
   if len(string) == 1:
      yield prefix + string            
   else:
      for i in range(len(string)):
         getPermutations(string[:i]+string[i+1:], prefix+string[i])  # <-----

forループでそれを繰り返す必要があります（@MizardXの投稿を参照してください。これは数秒で私を追い出しました！）

于 2008-10-29T23:54:51.923 に答える