回溯法--全排列

发布时间：2020-12-20 09:50:48 所属栏目：Python 来源：网络整理

导读：a=[1,2,3 ]n = len(a)res = [] def permutation(a,solution): # 注意，这里要用global修饰res，才能更新结果 global res if len(a)== 0: res.append(solution) return for i in range(len(a)): newsolution =solution+ [a[i]] new_a =a[:i]+a[i+1 :] permuta

a=[1,2,3]
n=len(a)
res=[]
def permutation(a,solution):
    #注意，这里要用global修饰res，才能更新结果
    global res
    if len(a)==0:
        res.append(solution)
        return
    for i in range(len(a)):
　　　　　newsolution=solution+[a[i]]
        new_a=a[:i]+a[i+1:]
        permutation(new_a,newsolution)
permutation(a,[])
print(res)
输出：
[[1,3],[1,3,2],[2,1,1],[3,1]]

基本思路：

其实对于回溯法，我们要从反向开始考虑。我们每次从原始数组中选择一个加入到结果中，当原始数组中（新建的）没有元素时（也就是len(a)==0，此时结果为[1,3]），我们得到了第一个排列，我们将这个排列加入到结果集中，然后返回上一步，也就是我们现在有[1,2]，再返回一步[1]，此时再加入3，再加入2，得到[1,

以此类推。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!