Python:将打印递归函数转换为生成器
Python: translating a printing recursive function into a generator
我找到了这个函数:
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)
在 Whosebug 上的 Trying to implement recursive Tower of Hanoi algorithm with arrays 此处。
现在我需要修改它,以便在每次迭代时产生 pegs
变量,而不是打印 start, target, 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
得到 "stuck" 在深度递归级别中,因此它会屈服于较不深度的递归而不是 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]]
这里唯一的 'trick' 是 yield from hanoi_yield
因为 hanoi_yield
是一个发电机。
不利方面:此 return 始终引用同一个列表并更改输入列表 pegs
(这只是 return 值)!这可能是不希望的或有用的......更多内容如下:
一个不改变第一个参数的版本 (pegs
) 和 return 每次都是一个单独的列表(因此可以在 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)
我找到了这个函数:
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)
在 Whosebug 上的 Trying to implement recursive Tower of Hanoi algorithm with arrays 此处。
现在我需要修改它,以便在每次迭代时产生 pegs
变量,而不是打印 start, target, 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
得到 "stuck" 在深度递归级别中,因此它会屈服于较不深度的递归而不是 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]]
这里唯一的 'trick' 是 yield from hanoi_yield
因为 hanoi_yield
是一个发电机。
不利方面:此 return 始终引用同一个列表并更改输入列表 pegs
(这只是 return 值)!这可能是不希望的或有用的......更多内容如下:
一个不改变第一个参数的版本 (pegs
) 和 return 每次都是一个单独的列表(因此可以在 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)