Python: menggunakan algoritma rekursif sebagai generator

Baru-baru ini saya menulis sebuah fungsi untuk menghasilkan urutan tertentu dengan batasan nontrivial. Masalahnya datang dengan solusi rekursif alami. Sekarang kebetulan, bahkan untuk input yang relatif kecil, urutannya beberapa ribu, jadi saya lebih suka menggunakan algoritme saya sebagai generator daripada menggunakannya untuk mengisi daftar dengan semua urutan.

Berikut ini contohnya. Misalkan kita ingin menghitung semua permutasi string dengan fungsi rekursif. Algoritme naif berikut mengambil 'penyimpanan' argumen ekstra dan menambahkan permutasi padanya setiap kali menemukannya:

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

(Tolong jangan pedulikan inefisiensi, ini hanya sebuah contoh.)

Sekarang saya ingin mengubah fungsi saya menjadi generator, yaitu untuk menghasilkan permutasi daripada menambahkannya ke daftar penyimpanan:

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

Kode ini tidak berfungsi (fungsi berperilaku seperti generator kosong).

Apakah saya melewatkan sesuatu? Apakah ada cara untuk mengubah algoritma rekursif di atas menjadi generator tanpa menggantinya dengan yang berulang ?

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

Atau tanpa akumulator:

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

Ini menghindari len(string)rekursi -deep, dan secara umum merupakan cara yang bagus untuk menangani generator-inside-generator:

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

flattenmemungkinkan kita untuk melanjutkan kemajuan di generator lain hanya yielddengan melakukannya, alih-alih mengulanginya dan yieldsetiap item secara manual.

Python 3.3 akan menambahkan yield fromsintaks, yang memungkinkan pendelegasian alami ke sub-generator:

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

Panggilan interior ke getPermutations - ini juga generator.

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])  # <-----

Anda perlu mengulanginya dengan for-loop (lihat posting @MizardX, yang membuat saya keluar beberapa detik!)