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

我发现此功能：

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

现在，我需要修改它，以便在每次迭代时都输出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)

最佳答案

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

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)