的Python：翻譯印刷遞歸函數到發電機

Question

我發現這個功能：

def hanoi(pegs, start, target, n): 
    assert len(pegs[start]) >= n, 'not enough disks on peg' 
    if n == 1: 
     pegs[target].append(pegs[start].pop()) 
     print '%i -> %i: %s' % (start, target, pegs) 
    else: 
     aux = 3 - start - target # start + target + aux = 3 
     hanoi(pegs, start, aux, n-1) 
     hanoi(pegs, start, target, 1) 
     hanoi(pegs, aux, target, n-1) 

在這裏Trying to implement recursive Tower of Hanoi algorithm with arrays在計算器上。

現在我需要修改它，以便代替打印start, target, pegs而不是每次迭代排除pegs變量。

例如，我希望這個輸出出來的新功能（漂亮印刷）的：

>>> list(hanoi([[120, 90, 60, 30], [], []])) 
[ [[120, 90, 60], [30], []], 
    [[120, 90], [30], [60]], 
    [[120, 90], [], [60, 30]], 
    [[120], [90], [60, 30]], 
    [[120, 30], [90], [60]], 
    [[120, 30], [90, 60], []], 
    [[120], [90, 60, 30], []], 
    [[], [90, 60, 30], [120]], 
    [[], [90, 60], [120, 30]], 
    [[60], [90], [120, 30]], 
    [[60, 30], [90], [120]], 
    [[60, 30], [], [120, 90]], 
    [[60], [30], [120, 90]], 
    [[], [30], [120, 90, 60]], 
    [[], [], [120, 90, 60, 30]], 
] 

這是我嘗試修改它：

def hanoi(pegs, start, target, n): 
    assert len(pegs[start]) >= n, 'not enough disks on peg' 
    if n == 1: 
     pegs[target].append(pegs[start].pop()) 
     yield pegs 
    else: 
     aux = 3 - start - target # start + target + aux = 3 
     hanoi(pegs, start, aux, n-1) 
     hanoi(pegs, start, target, 1) 
     hanoi(pegs, aux, target, n-1) 

但是，（輸入釘號碼因爲圖形的目的而變得更大）：

>>> pegs = [[120, 90, 60, 30], [], []] 
>>> print(list(hanoi(pegs, 0, 2, 4))) 
[] 

輸出只是一個空的列表。

試圖讓通過[:]名單的副本沒有幫助，而且我留下很迷茫，也許print可以隨時打印出來，但yield被「卡住」內心深處遞歸級別，所以它產生較少的深遞歸而不是outside。此外，用列表與append不起作用：

def hanoi(pegs, start, target, n): 
    assert len(pegs[start]) >= n, 'not enough disks on peg' 
    out = [] 
    if n == 1: 
     pegs = pegs[:] 
     pegs[target].append(pegs[start].pop()) 
     out.append(pegs) 
    else: 
     aux = 3 - start - target # start + target + aux = 3 
     hanoi(pegs, start, aux, n-1) 
     hanoi(pegs, start, target, 1) 
     hanoi(pegs, aux, target, n-1) 
    return out 

我也嘗試以下建議，從Python: using a recursive algorithm as a generator

def hanoi(pegs, start, target, n): 
    assert len(pegs[start]) >= n, 'not enough disks on peg' 
    if n == 1: 
     pegs = pegs[:] 
     pegs[target].append(pegs[start].pop()) 
     yield pegs 
    else: 
     aux = 3 - start - target # start + target + aux = 3 
     for i in hanoi(pegs, start, aux, n-1): yield i 
     for i in hanoi(pegs, start, target, 1): yield i 
     for i in hanoi(pegs, aux, target, n-1): yield i 

通過從嵌套循環for收益，但是失敗了。

如何編寫這樣的生成器（我需要用於圖形目的）？

發電機將用於這樣的：

pegs = [[120, 90, 60, 30], [], []] 
positions = hanoi(pegs, 0, 2, 4) 

for position in positions: 
    screen.fill((255, 255, 255)) 

    print(index, peg_history[index]) 
    for i, pegs in enumerate(position): 
     display_pegs(pegs, 100 + 180*i, 300, screen) 
    pygame.display.update() 
    time.sleep(0.5) 

Answer 1

發電機版本看起來是這樣的：

def hanoi_yield(pegs, start, target, n): 
    # pegs will be modified! 
    assert len(pegs[start]) >= n, 'not enough disks on peg' 

    if n == 1: 
     pegs[target].append(pegs[start].pop()) 
     yield pegs 
    else: 
     aux = 3 - start - target # start + target + aux = 3 
     yield from hanoi_yield(pegs, start, aux, n-1) 
     yield from hanoi_yield(pegs, start, target, 1) 
     yield from hanoi_yield(pegs, aux, target, n-1) 

pegs = [[120, 90, 60, 30], [], []] 
for item in hanoi_yield(pegs, 0, 2, 4): 
    print(item) 

與輸出：

[[120, 90, 60], [30], []] 
[[120, 90], [30], [60]] 
[[120, 90], [], [60, 30]] 
[[120], [90], [60, 30]] 
[[120, 30], [90], [60]] 
[[120, 30], [90, 60], []] 
[[120], [90, 60, 30], []] 
[[], [90, 60, 30], [120]] 
[[], [90, 60], [120, 30]] 
[[60], [90], [120, 30]] 
[[60, 30], [90], [120]] 
[[60, 30], [], [120, 90]] 
[[60], [30], [120, 90]] 
[[], [30], [120, 90, 60]] 
[[], [], [120, 90, 60, 30]] 

唯一的 '絕招'這裏是yield from hanoi_yield，因爲hanoi_yield是一個發生器。

反面：這會一直返回對同一個列表的引用並更改輸入列表pegs（它只是返回值）！可能不希望的或有用...更多下面：

---

不改變的第一個參數（pegs）每次返回一個單獨的列表（並因此在list構造函數中使用）的版本。我必須添加一個輔助變量_work_pegs，因爲算法需要更改此列表。 pegs現在不變。我也yield結果的deepcopy（我們正在處理在這裏列出的名單;定期拷貝是行不通的）：

from copy import deepcopy 

def hanoi_yield(pegs, start, target, n, _work_pegs=None): 

    if _work_pegs is None: 
     _work_pegs = deepcopy(pegs) 
     # or (this way pegs could be a tuple of tuples): 
     # _work_pegs = [list(item) for item in pegs] 

    assert len(_work_pegs[start]) >= n, 'not enough disksdef on peg' 

    if n == 1: 
     _work_pegs[target].append(_work_pegs[start].pop()) 
     yield deepcopy(_work_pegs) 
     # or (returning tuples might be nice...): 
     # yield tuple(tuple(item) for item in _work_pegs) 
    else: 
     aux = 3 - start - target # start + target + aux = 3 
     yield from hanoi_yield(pegs, start, aux, n-1, _work_pegs) 
     yield from hanoi_yield(pegs, start, target, 1, _work_pegs) 
     yield from hanoi_yield(pegs, aux, target, n-1, _work_pegs) 

最後這個作品：

pegs = [[120, 90, 60, 30], [], []] 
lst = list(hanoi_yield(pegs, 0, 2, 4)) 
print(lst)