[解決済み] Python: 再帰的アルゴリズムをジェネレータとして使用する

質問

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

以下に例を示します。再帰的な関数で文字列のすべての並べ換えを計算したいとします。以下の素朴なアルゴリズムは追加の引数'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

このコードでは ではなく が動作しません (この関数は空のジェネレータのように動作します)。

私は何かを見逃しているのでしょうか？ 上記の再帰的アルゴリズムをジェネレータにする方法はありますか？ に置き換える方法はありますか？ ?

どのように解決するのですか？

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