Python - 回溯

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

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

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']

推荐教程

Python 2.7.X 手册

Python 2.7基础语法、实例讲解

Python实用手册

Python 实战演练、轻松入门

PySpark教程

Apache Spark是一个闪电般快速的实时处理框架

Seaborn教程

Seaborn是Python中的可视化库

Flask教程

Flask是一个用Python编写的Web应用程序框架

Django教程

Django是一个Web开发框架

Web2py教程

Web2py被定义为一个免费的开源Web开发框架

Scrapy教程

Scrapy是一个用Python编写的快速,开源的网页爬虫框架

Python3 教程

常被称为Python 3000,或简称Py3k

Python数据结构

算法是一步一步的指令集来处理特定用途的数据