Python：使用遞歸算法作爲生成器

Question

最近我寫了一個函數來生成具有非平凡約束的特定序列。問題出現在自然遞歸解決方案中。現在碰巧，即使是相對較小的輸入，序列也有數千個，因此我寧願將我的算法用作生成器，而不是用它來填充所有序列的列表。

這裏是一個例子。假設我們想用遞歸函數計算一個字符串的所有排列。下面天真的算法需要一個額外的參數「存儲設備」，並追加置換到它時，它發現一個：

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 

此代碼不工作（該函數的行爲像一個空發生器）。

我錯過了什麼嗎？ 有沒有辦法將上面的遞歸算法變成一個生成器而不用迭代器代替它？

Answer 1

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 

Answer 2

內部調用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發佈，這一柄我出去被秒！）

Answer 3

這就避免了len(string) - 深遞歸，並且一般一個不錯的方法來處理生成，內部發電機：

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 

flatten允許我們通過簡單的yield荷蘭國際集團它，而不是通過它迭代和yield手動荷蘭國際集團各項目繼續在另一個生成的進展。

---

的Python 3.3將增加yield 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])