python - 如何收集递归回溯的结果?
问题描述
我正在自学递归回溯。对于骰子求和问题,我不知道如何优雅地收集结果。
作为参考,这是我的代码,它只打印任何符合标准的骰子。理想情况下,我想改变它,而不是打印输出,我可以建立一个列表,列出那些选择的骰子并返回它。
下面是不符合我要求的代码
def dice_sum(num_dice: int, target_sum: int) -> None:
dice_sum_helper(num_dice, target_sum, [])
def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int]) -> None:
if num_dice == 0 and sum(chosen) == target_sum:
print(chosen)
elif num_dice == 0:
pass
else:
for i in range(1, 7):
chosen.append(i)
dice_sum_helper(num_dice - 1, target_sum, chosen)
chosen.pop()
相反,我希望它做这样的事情
from typing import List
DiceResult = List[List[int]]
def dice_sum(num_dice: int, target_sum: int) -> DiceResult:
return dice_sum_helper(num_dice, target_sum, [])
def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int]) -> DiceResult:
if num_dice == 0 and sum(chosen) == target_sum:
# Return the value that meets the constraints
return chosen
elif num_dice == 0:
pass
else:
for i in range(1, 7):
chosen.append(i)
# Return the result of my recursive call and build the list of lists?
result = dice_sum_helper(num_dice - 1, target_sum, chosen)
return result.append(result)
# End of that logic
chosen.pop()
我正在寻找要使用的理论或模式,而不是确切的代码。如果不使用外部列表,我无法完全获取代码来收集和附加每个结果。
解决方案
您可以利用yield
并yield from
从您的函数返回结果:
from typing import List
def dice_sum(num_dice: int, target_sum: int) -> None:
yield from dice_sum_helper(num_dice, target_sum, [])
def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int]) -> None:
if num_dice == 0 and sum(chosen) == target_sum:
yield chosen[:]
elif num_dice == 0:
pass
else:
for i in range(1, 7):
chosen.append(i)
yield from dice_sum_helper(num_dice - 1, target_sum, chosen)
chosen.pop()
# you can store the results e.g. to list:
# results = list(dice_sum(3, 12))
for dices in dice_sum(3, 12):
for d in dices:
print('{: ^4}'.format(d), end='|')
print()
印刷:
1 | 5 | 6 |
1 | 6 | 5 |
2 | 4 | 6 |
2 | 5 | 5 |
2 | 6 | 4 |
3 | 3 | 6 |
3 | 4 | 5 |
3 | 5 | 4 |
3 | 6 | 3 |
4 | 2 | 6 |
4 | 3 | 5 |
4 | 4 | 4 |
4 | 5 | 3 |
4 | 6 | 2 |
5 | 1 | 6 |
5 | 2 | 5 |
5 | 3 | 4 |
5 | 4 | 3 |
5 | 5 | 2 |
5 | 6 | 1 |
6 | 1 | 5 |
6 | 2 | 4 |
6 | 3 | 3 |
6 | 4 | 2 |
6 | 5 | 1 |
推荐阅读
- mongodb - $arrayElemAt 的第一个参数必须是一个数组
- uml - UML 关联意义
- eclipse - EGit 中“切换到”的目的是什么?
- tfs - 清理旧的 TFS 安装
- regex - 正则表达式:如何匹配整个单词,其中只有一个破折号不超过 1 个破折号?
- mysql - 在 Where 子句更好还是 ON 子句上编写条件?
- bash - -bash: gshuf: command not found 没有这样的文件或目录
- json - 即使使用 try/catch 块,错误也会冒泡到 Mocha 测试
- apache-flink - 使用java rest客户端无法在Flink 1.5中上传jar
- asp.net - ASP.NET 4.7 表单身份验证失败,提供的票证无效