Skip to main content
 首页 » 编程设计

Python:将打印递归函数转换为生成器

2025年02月15日13xiaohuochai

我找到了这个函数:

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在 StackOverflow 上。

现在我需要修改它,以便在每次迭代时生成 pegs 变量,而不是打印 start, target, pegs 。

例如,我期望新函数的输出( pretty-print ):

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

但是,(出于图形目的,输入的 Hook 数字有点大):

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

输出只是一个空列表。

尝试通过 [:] 复制列表没有帮助,我很困惑,也许 print 总能打印出来,但是 yield 被“卡住”在深层递归级别中,因此它会屈服于深度较低的递归,而不是外部。同样使用带有 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) 

请您参考如下方法:

生成器版本可能如下所示:

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

这里唯一的“技巧”是从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)