黑马程序员技术交流社区

标题: 【广州Python】Python-回溯 [打印本页]

---

作者: yangrui    时间: 2019-2-14 12:23
标题: 【广州Python】Python-回溯


回溯
回溯是递归的一种形式。但它涉及选择任何可能性的唯一选择。我们首先选择一个选项并从中退出，如果我们达到了一个状态，那么我们可以得出结论：这个特定的选项不能提供所需的解决方案。我们通过遍历每个可用选项来重复这些步骤，直到获得所需的解决方案。

案例
以下例子是查找给定字母集合的所有可能排列顺序的示例。当我们选择一对时，我们应用回溯来验证是否已经创建了该确切的一对。如果尚未创建，则将该对添加到答案列表中，否则将被忽略。

[Python] 纯文本查看 复制代码

def permute(a, s):

    if a == 1:

        return s

    else:

        return [ y + x

                 for y in permute(1, s)

                 for x in permute(a - 1, s)

                 ]



print(permute(1, ["a","b","c"]))

print(permute(2, ["a","b","c"]))

上述代码输出结果为：

[Python] 纯文本查看 复制代码

['a', 'b', 'c']

['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2