我找到了这个函数:
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)
