Python 回溯
Python 回溯详细操作教程
回溯是递归的一种形式。但这涉及从任何可能性中仅选择选项。我们首先选择一个选项并从中回溯,如果我们得出的结论是,该特定选项未提供所需的解决方案,则我们从中回溯。我们通过遍历每个可用选项来重复这些步骤,直到获得所需的解决方案。
以下是查找给定字母集的所有可能排列顺序的示例。当我们选择一个对时,我们将应用回溯来验证该对是否已经创建。如果尚未创建,则该对将添加到答案列表,否则将被忽略。
# Filename : example.py
# Copyright : 2020 By Lidihuo
# Author by : www.lidihuo.com
# Date : 2020-08-15
def permute(list, s):
if list == 1:
return s
else:
return [ y + x
for y in permute(1, s)
for x in permute(list - 1, s)
]
print(permute(1, ["a","b","c"]))
print(permute(2, ["a","b","c"]))
运行结果如下:
['a', 'b', 'c']
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']