问题:输入列表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,看了之后醍醐灌顶。
先帖一个正确解法:
""" 回溯算法模板: from: labuladong公众号 result = [] def backtrack(选择列表,路径): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择(要去重,判断该选择是否已经在选择列表中,已经选过的不要选) backtrack(选择列表,路径) 选择列表.removelast() #撤销这个选择,因为要重新从头开始(回溯树的跟节点) """ import copy def backtrack(L,path): if len(path)==len(L): c = copy.copy(path) # 注意这里不是直接将path加到res中,而是深拷贝了一个对象 res.append(c) # res.append(path) # print(res) return for i in L: if i in path: continue else: path.append(i) backtrack(L,path) #path = path[:-1] path.pop() # 注意此处“撤销”选择的方法 if __name__ == "__main__": res = [] L = [1,2,3] backtrack(L,[]) print(res)
输出:
以上算法使用python
的深拷贝,假如不使用会怎样呢?
看下面代码:
def backtrack(L,path): if len(path)==len(L): # c = copy.copy(path) # res.append(c) res.append(path) print(res) return for i in L: if i in path: continue else: path.append(i) backtrack(L,path) #path = path[:-1] path.pop() # 注意此处“撤销”选择的方法 if __name__ == "__main__": res = [] L = [1,2,3] backtrack(L,[]) print(res)
此时的输出:
这个结果着实令人疑惑, 仔细分析后发现是python的浅拷贝搞的鬼。当我们判断len(path) == L时,就将path append
到res中,但事实上,res中存放的只是path的一个指针,当我们对path进行“撤销选择”时,即path.pop()
,会连带着将res中元素也修改掉,这显然是不合理的。仔细看的话其实每一次输出的第一列组合起来刚好是全排列。
再看一个错误示例,在撤销选择时不适用path.pop()
,而是path = path[:-1]
。
import copy def backtrack(L,path): if len(path)==len(L): c = copy.copy(path) # 注意这里不是直接将path加到res中,而是深拷贝了一个对象 res.append(c) # res.append(path) print(res) return for i in L: if i in path: continue else: path.append(i) backtrack(L,path) path = path[:-1] # 换一种“撤销”选择的方法 #path.pop() # 注意此处“撤销”选择的方法 if __name__ == "__main__": res = [] L = [1,2,3] backtrack(L,[]) print(res)
此时的输出:
更加令人疑惑,使用debug
调试后发现,path撤销选择,即path = path[:-1]
没起到作用,在向上回溯的过程中,由于函数签名是
backtrack(L,path)
由于path是以一个参数的形式传入函数的,所以每一层递归调用中,使用的path应该是同一个,当我们用path.pop()
撤销选择时,每一层的递归栈中,path应该同时发生变化。(可以这么类比,当我第一轮递归,path=[1,2,3]后,向上递归时,合理思考应该将path依次变成[1,2]、[1],这样才能继续向里面添加元素,组成不同的排列),但使用path = path[:-1],调试发现除了本层递归栈以外,其他递归栈的path并未发生变化:
这次是深拷贝的锅,我们合理怀疑path=path[:-1],应该是生成了一个新的对象,即=左右的path并不是同一个对象,因此每层递归树的path不会改变,来验证一下:
到此这篇关于python回溯算法实现全排列小练习分享的文章就介绍到这了,更多相关python回溯算法实现全排列内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
X 关闭
X 关闭
- 15G资费不大降!三大运营商谁提供的5G网速最快?中国信通院给出答案
- 2联想拯救者Y70发布最新预告:售价2970元起 迄今最便宜的骁龙8+旗舰
- 3亚马逊开始大规模推广掌纹支付技术 顾客可使用“挥手付”结账
- 4现代和起亚上半年出口20万辆新能源汽车同比增长30.6%
- 5如何让居民5分钟使用到各种设施?沙特“线性城市”来了
- 6AMD实现连续8个季度的增长 季度营收首次突破60亿美元利润更是翻倍
- 7转转集团发布2022年二季度手机行情报告:二手市场“飘香”
- 8充电宝100Wh等于多少毫安?铁路旅客禁止、限制携带和托运物品目录
- 9好消息!京东与腾讯续签三年战略合作协议 加强技术创新与供应链服务
- 10名创优品拟通过香港IPO全球发售4100万股 全球发售所得款项有什么用处?