全排列组合实现方法
上篇24点游戏通过多重循环遍历出所有可能的组数字组合。
# 数字列表
b = [2,3, 12, 13]
# 结果列表
l = []
for i in range(4):
for j in range(4):
for m in range(4):
for n in range(4):
# 通过索引位置不同，确定是不同的数字
if i!=j and i!=m and i!=n and j!=m and j!=n and m!=n:
l.append([b[i], b[j], b[m], b[n]])
print(l)[[2, 3, 12, 13], [2, 3, 13, 12], [2, 12, 3, 13], [2, 12, 13, 3], [2, 13, 3, 12], [2, 13, 12, 3], [3, 2, 12, 13], [3, 2, 13, 12], [3, 12, 2, 13], [3, 12, 13, 2], [3, 13, 2, 12], [3, 13, 12, 2], [12, 2, 3, 13], [12, 2, 13, 3], [12, 3, 2, 13], [12, 3, 13, 2], [12, 13, 2, 3], [12, 13, 3, 2], [13, 2, 3, 12], [13, 2, 12, 3], [13, 3, 2, 12], [13, 3, 12, 2], [13, 12, 2, 3], [13, 12, 3, 2]]
如果是3个数字，代码就更简单了。
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
这种全排列的问题，除了上面这种全部遍历的方法，网上看到还有使用回溯算法来解决的。
刚好最近在研究算法，试了一下，还挺有意思的，其实就是遍历树。
def backtrack(choiceList, track):
# 如果选择列表为空，说明已经完成一个组合
if len(choiceList)==0:
print("排列结果：",track)
else:
# 遍历每一个数字
for i in range(0,len(choiceList)):
choice = choiceList[i]# 选择一个数
track.append(choice) # 加入 track
choiceList.remove(choice)#删除该数字
# 递归继续选择下一个数字
backtrack(choiceList, track)
# 回溯过程
choiceList.insert(i,choice)# 将删除的元素重新加入choiceList
track.remove(choiceList[i])# 从 track 中撤销上面的选择
choiceList = [1, 2,3] # 待选择列表
track = [] # 已经选择的数列表
backtrack(choiceList, track)
排列结果：[1, 2, 3]
排列结果：[1, 3, 2]
排列结果：[2, 1, 3]
排列结果：[2, 3, 1]
排列结果：[3, 1, 2]
排列结果： [3, 2, 1]光看代码其实挺难理解的，因为有递归在里面。配合图片加打印的文字会更好理解
-----开始选择------
已经选择: [1] 剩余选择: [2, 3]
-----结束选择------
-----开始选择------
已经选择: [1, 2] 剩余选择: [3]
-----结束选择------
-----开始选择------
已经选择: [1, 2, 3] 剩余选择: []
-----结束选择------
排列结果：[1, 2, 3]
-----开始回退------
已经选择: [1, 2] 剩余选择: [3]
-----结束回退------
-----开始回退------
已经选择: [1] 剩余选择: [2, 3]
-----结束回退------
-----开始选择------
已经选择: [1, 3] 剩余选择: [2]
-----结束选择------
-----开始选择------
已经选择: [1, 3, 2] 剩余选择: []
-----结束选择------
排列结果：[1, 3, 2]
-----开始回退------
已经选择: [1, 3] 剩余选择: [2]
-----结束回退------
-----开始回退------
已经选择: [1] 剩余选择: [2, 3]
-----结束回退------
-----开始回退------
已经选择: [] 剩余选择: [1, 2, 3]
-----结束回退------
-----开始选择------
已经选择: [2] 剩余选择: [1, 3]
-----结束选择------
-----开始选择------
已经选择: [2, 1] 剩余选择: [3]
-----结束选择------
-----开始选择------
已经选择: [2, 1, 3] 剩余选择: []
-----结束选择------
排列结果：[2, 1, 3]
-----开始回退------
已经选择: [2, 1] 剩余选择: [3]
-----结束回退------
-----开始回退------
已经选择: [2] 剩余选择: [1, 3]
-----结束回退------
-----开始选择------
已经选择: [2, 3] 剩余选择: [1]
-----结束选择------
-----开始选择------
已经选择: [2, 3, 1] 剩余选择: []
-----结束选择------
排列结果：[2, 3, 1]
-----开始回退------
已经选择: [2, 3] 剩余选择: [1]
-----结束回退------
-----开始回退------
已经选择: [2] 剩余选择: [1, 3]
-----结束回退------
-----开始回退------
已经选择: [] 剩余选择: [1, 2, 3]
-----结束回退------
-----开始选择------
已经选择: [3] 剩余选择: [1, 2]
-----结束选择------
-----开始选择------
已经选择: [3, 1] 剩余选择: [2]
-----结束选择------
-----开始选择------
已经选择: [3, 1, 2] 剩余选择: []
-----结束选择------
排列结果：[3, 1, 2]
-----开始回退------
已经选择: [3, 1] 剩余选择: [2]
-----结束回退------
-----开始回退------
已经选择: [3] 剩余选择: [1, 2]
-----结束回退------
-----开始选择------
已经选择: [3, 2] 剩余选择: [1]
-----结束选择------
-----开始选择------
已经选择: [3, 2, 1] 剩余选择: []
-----结束选择------
排列结果：[3, 2, 1]
-----开始回退------
已经选择: [3, 2] 剩余选择: [1]
-----结束回退------
-----开始回退------
已经选择: [3] 剩余选择: [1, 2]
-----结束回退------
-----开始回退------
已经选择: [] 剩余选择: [1, 2, 3]
-----结束回退------上面的方法仅仅只是为了更好看懂回溯过程，除此之外，还可以利用标记列表来记录已经访问过的。
def backtrack(choice,choiceList, visited, answer):
if choice==len(choiceList):
print(answer)
for i in range(0,len(choiceList)):
if visited[i]==True:
# 选择一个数
answer[choice] = choiceList[i] # 添加选择数据到列表中
visited[i] =False # 标记该数字已经选择
backtrack(choice+1,choiceList, visited, answer)
# 回退一个数
answer[choice] = 0
visited[i] =True
visited = [True,True,True] # 标记列表，默认选择
choiceList = [1,2,3] # 待选择列表
answer = [0 for x in range(3)] # 答案列表
choice = 0 # 从索引0开始
backtrack(choice,choiceList,visited,answer)(全文完)
欢迎转载，转载请注明出处！
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-05-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读