停止遞歸生成器和排列

作爲一項練習，我一直在嘗試各種方式來生成Python中列表的所有排列 - 遞歸，非遞歸... - 並將性能與itertools.permutations()進行比較。但我在使用遞歸方法，它不與StopIteration異常乾淨完成，而是的發電機版本麻煩拋出一個IndexError：停止遞歸生成器和排列

def spawnperms(alist): 
    """same algorithm as recursive option, but a generator""" 
    if (alist == []): 
     yield [] 
    for perm in spawnperms(alist[:-1]): 
     for i in range(len(perm)+1): 
      yield perm[:i] + [alist[-1]] + perm[i:]

從Python解釋器調用此：

>>> for i in spawnperms(range(3)): 
...  print i 
... 
[2, 1, 0] 
[1, 2, 0] 
[1, 0, 2] 
[2, 0, 1] 
[0, 2, 1] 
[0, 1, 2] 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "<stdin>", line 5, in spawnperms 
    File "<stdin>", line 5, in spawnperms 
    File "<stdin>", line 5, in spawnperms 
    File "<stdin>", line 7, in spawnperms 
IndexError: list index out of range

Ouch。我嘗試着用pdb來完成它，它幾乎在我的大腦中創建了一個堆棧溢出，但是我的理解是遞歸「向下」到空列表，然後外部（我認爲）for循環用完索引。

如何更正我的代碼？

編輯：馬克拜爾斯看似簡單的正確答案一個學習就是乾淨的編碼習慣，可以防止錯誤。如果我在if之後系統地使用了else，無論我是否認爲可以重新訪問該狀況，都不會發生這種情況。它仍然感覺非常愚蠢！

來源

2010-08-10 chryss

要測試列表是否爲空，「if not alist：」就足夠了。 – kennytm 2010-08-10 11:09:07

是的，的確如此。我通常會這樣做，但專注於其他事情。不過，你是完全正確的。 – chryss 2010-08-10 11:30:42

你缺少一個else：

if (alist == []): 
    yield [] 
else: 
    for ...

這是因爲yield不會以同樣的方式作爲return行爲。當您請求下一個值時，在yield語句後繼續執行。

來源

2010-08-10 11:07:50

嗯......毫無疑問，「yield」和「return」之間的區別正是我認爲我不需要「else」的原因。但我認爲我的邏輯是有缺陷的。 – chryss 2010-08-10 11:09:27

:)是的，我的邏輯完全有缺陷。非常感謝 - 我現在覺得多麼愚蠢。 – chryss 2010-08-10 11:11:12

停止遞歸生成器和排列

回答

相關問題