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) 用於存儲中的排列:打印排列 

(請不要在意效率低下,這只是一個例子。)

現在我想把我的函數變成一個生成器,即產生一個排列而不是將它附加到存儲列表中:

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 

這段代碼工作(該函數的行為類似於 em pty 生成器)。

我錯過了什麼嗎?有沒有辦法將上述遞歸算法變成生成器而不用迭代算法替換它