python 回溯法,回溯算法求全排列
本文主要和大家分享一个python回溯算法实现全排列的小练习。根据例子：输入列表L(无重复元素)输出L的全排列来学习，有需要的朋友可以参考一下。
问题：输入列表L(没有重复的元素)并输出L的完整排列
如输入：L=[1，2，3]
则输出：[[1，2，3]，[1，3，2]，[2，1，3]，[2，3，1]，[3，1，2]，[3，2，1]
整个安排问题可以用回溯法解决。详细分析可参考东哥微信官方账号：labuladong。看完之后，你会清醒的。
先帖一个正确解法：
回溯算法模板：
来自： labuladong微信官方账号
结果=[]
定义回溯(选择列表，路径):
如果满足结束条件：
Result.add(路径)
返回
在选择列表：中选择for
进行选择(如果要去掉权重，判断选择是否已经在选择列表中，不要选择已经选中的)
回溯(选择列表，路径)
选择列表。removelast() #来撤销这个选择，因为你必须从头开始(回溯树的以下节点)。
导入副本
定义回溯(L，路径):
if len(path)==len(L):
C=copy.copy(path) #注意，这里不是直接给res添加path，而是深度复制一个对象。
资源追加(c)
# res.append(路径)
#打印(分辨率)
返回
对于L:中的I
如果我在：路
继续
else:
path.append(i)
回溯(L，路径)
#path=path[:-1]
Path.pop() #注意如何在此处“撤消”选择。
if __name__==__main__:
res=[]
L=[1，2，3]
回溯(L，[])
打印(分辨率)
输出：
上面的算法使用了python的深度拷贝。如果没有呢？
看下面代码：
定义回溯(L，路径):
if len(path)==len(L):
# c=copy.copy(路径)
# res.append(c)
资源追加(路径)
打印(分辨率)
返回
对于L:中的I
如果我在：路
继续
else:
path.append(i)
回溯(L，路径)
#path=path[:-1]
Path.pop() #注意如何在此处“撤消”选择。
if __name__==__main__:
res=[]
L=[1，2，3]
回溯(L，[])
打印(分辨率)
此时的输出：
这个结果真的很混乱。仔细分析后发现，python的浅拷贝才是内鬼。当我们判断len(path)==L时，我们将path追加到res中，但实际上res中只存储了path的一个指针，当我们“取消选择”path即path.pop()时，RES中的元素也会被修改，这显然是不合理的。仔细看的话，其实每个输出的第一列只是完整排列而已。
再看另一个错误例子，取消选择时path.pop()不适用，但path=path[:-1]。
导入副本
定义回溯(L，路径):
if len(path)==len(L):
C=copy.copy(path) #注意，这里不是直接给res添加path，而是深度复制一个对象。
资源追加(c)
# res.append(路径)
打印(分辨率)
返回
对于L:中的I
如果我在：路
继续
else:
path.append(i)
回溯(L，路径)
Path=path[:-1] #更改“撤消”选择的方法。
#path.pop() #注意如何在此处“撤消”选择。
if __name__==__main__:
res=[]
L=[1，2，3]
回溯(L，[])
打印(分辨率)
此时的输出：
更让人摸不着头脑。用debug调试后发现路径取消选择，即path=path [3360-1]不起作用。在回溯过程中，因为函数签名是
回溯(L，路径)
由于path是作为参数传递给函数的，所以每一层递归调用中使用的路径应该是相同的。当我们用path.pop()取消选择时，递归栈中每一层的路径应该是同时变化的。(可以类比的是，当我在第一轮后递归上去，path=[1，2，3]时，有理由认为我应该把路径依次改成[1，2]和[1]，这样我就可以继续给它加元素，形成不同的排列)，但是使用path=path [3360-1]，调试发现除了这一层的递归栈，
这次是深抄锅。我们有理由怀疑path=path[:-1]。应该是生成了新的对象，也就是=周围的路径不是同一个对象，所以每棵递归树的路径都不会变，来验证一下：.
关于python回溯算法实现全排列的分享练习这篇文章到此为止。关于python回溯算法实现全排列的更多信息，请搜索热门IT软件开发工作室之前的文章或者继续浏览下面的相关文章。希望大家以后多多支持热门IT软件开发工作室！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。