首页 > 代码库 > python实现基础的深度优先搜索(DFS, depth first search)解决数的全排列问题
python实现基础的深度优先搜索(DFS, depth first search)解决数的全排列问题
数的全排列，是一个很简单的问题，平时我们用笔用纸就能列出答案，但是数列位多的时候，排列的结果就有非常多了，例如有1,2,3,4,5,6,7,8,9这一个数列，有9个数字，则有9!(9的阶乘)这么多种结果。那是非常大的。今天我就来介绍用深度优先搜索来解决这个数的全排列的问题。
深度优先搜索
首先简单介绍一下深度优先搜索，深度优先搜索的关键在于当下该如何做，至于下一步如何做，就与当下做的一样。深度优先搜索的基本模型为：
dfs(step): 判断边界：执行相关操作，返回 尝试每一种可能 for( i = 1; i <=n; i++): 继续下一步 dfs(step+1) 返回
数的全排列问题
回到数的全排列的问题。注：以下代码用来介绍程序核心思想，并不能直接运行，只有完整代码才能执行，step从1开始算。
我们用一个数组book=[]来记录我们那个数字已经选中了。用result来记录我们的结果。
首先，我们先来解决最简单的问题：将没有的选中的数字选一个出来，放到对应的数位上。所以将下面的代码翻译过来，就是将第step位设置为i+1(i是从0开始的，所以要加一，假设我们的数列没有0,每个数不重复)，并将i标记为已选中(book[i] = 1)
for i in range(n): if book[i] == 0: result[step] = i+1 book[i] = 1
然后，处理下一步：
def dfs(step): for i in range(n): if book[i] == 0: a[step] = i book[i] = 1 dfs(step+1) book[i] = 0
最后处理边界情况，当步数step与数列位数+1相等时，输出结果：
if step == n+1: printf result return
不停的重复以上的步骤，就能列出所有的结果
接下来是完整的代码：
# -*- coding:utf8 -*-‘‘‘简介：本程序主要简单实现深度优先搜索算法(depth first search) 并用解决数的全排列的问题。实现方法：递归作者：陈栋权2016/9/24 第一次发布‘‘‘class DFS(object): ‘‘‘ numlen: 为有几位数字，如3,则为1,2,3 result: 用来保存个序列的结果 book: 用来判断那个数字已经排列了 ‘‘‘ def __init__(self, n): self.numlen = n self.result = [0 for i in range(n)] self.book = [0 for i in range(n)] def dfs(self, s): step = s-1 if step == self.numlen: r = ‘‘ for i in range(self.numlen): r += str(self.result[i]) print r return # 用来尝试每种可能，即第step位的数为i for i in range(self.numlen): if self.book[i] == 0: self.result[step] = i+1 self.book[i] = 1 self.dfs(s+1) self.book[i] = 0 return
python实现基础的深度优先搜索(DFS, depth first search)解决数的全排列问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。