昨天 下午朋友發(fā)了我一道LeetCode面試題：
給定一個(gè)沒(méi)有重復(fù)的數(shù)字序列，返回其所有可能的全排列劳吠。示例:
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
我一看紫岩，這很簡(jiǎn)單啊，而且題目要求也很清晰，就打算五分鐘之內(nèi)寫(xiě)完發(fā)給他慰毅。
然而寫(xiě)了二十分鐘，居然扎阶，沒(méi)有汹胃，寫(xiě)，出东臀，來(lái)着饥！
我好菜啊…… （果然算法題是我的噩夢(mèng)）
網(wǎng)上看了一圈，發(fā)現(xiàn)別人的解法涉及到交換位置惰赋，講的也不太清楚的樣子宰掉。下班在地鐵上呵哨，我就開(kāi)動(dòng)了并不聰明的腦筋，好好想了一下轨奄。
明確問(wèn)題
全排列是一道高中數(shù)學(xué)必備的排列組合問(wèn)題孟害。我們知道：對(duì)一個(gè)去重列表的所有的可能情況，是 n挪拟！
假設(shè)列表有六個(gè)元素挨务，那么第一個(gè)元素的選擇可能有六種情況，第二個(gè)有剩下的五種玉组，第三個(gè)有四種……然后依次相乘得到所有的情況數(shù)谎柄。
或者從相反方向來(lái)建立，如果列表中只有一個(gè)數(shù)惯雳，那么只有唯一一種排列方式朝巫；
如果有兩個(gè)數(shù)字ab，那么就有a吨凑，b 和b捍歪，a兩種排列方式；
這個(gè)時(shí)候鸵钝，可以認(rèn)為是結(jié)果的第一位有兩種選擇：選a或者b糙臼，剩下的一位就是上面的一種排列方式。
這么看可能還不夠直觀恩商，接下來(lái)我們看abc三個(gè)數(shù)字的情況：
第一位有a变逃，b，c三種可能性怠堪，我們?nèi)绻舫隽薬放在結(jié)果第一位上揽乱，剩下的后兩位就是b，c的組合結(jié)果粟矿，由上述兩種數(shù)字排列可知凰棉，此時(shí)二，三位可以是b陌粹，c或者c撒犀，b排列，這就是兩種情況掏秩；接下來(lái)把第一位換成b或舞，剩下兩位就是a，c或者c蒙幻，a排列映凳；選擇c同理……
如果有abcd四個(gè)數(shù)字，那么第一位可以選擇abcd任意一個(gè)邮破，剩下三位就是剩下三個(gè)數(shù)字在上一步的全排列诈豌。
實(shí)際上仆救，我們?nèi)帕校褪窃趎-1的那一層排列情況上再構(gòu)建了一層队询，第一位的數(shù)字永遠(yuǎn)有n種可能性派桩，剩下的幾位就是上一步推出的n-1層排列組合結(jié)果，填進(jìn)去就好了蚌斩。
需要用到遞歸解法。遞歸的終點(diǎn)是：在只剩一個(gè)數(shù)字的情況下返回這個(gè)數(shù)字范嘱，列表為空返回空送膳。
代碼如下：
import copy
def permuation(x: list):
result = []
if not x:
return
if len(x) == 1:
return [x]
for num in x:
new_list = copy.copy(x)
new_list.remove(num)
for l in permuation(new_list):
if l:
res = [num]
res.extend(l)
result.append(res)
return result
print(permutation([1,2,3]))
>> [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
python由于自身特性，對(duì)于列表list的操作時(shí)一定要牢記：list在python中是可變對(duì)象丑蛤，意味著如果想要給新列表賦值叠聋，需要用到copy來(lái)實(shí)現(xiàn)復(fù)制已有列表的功能，否則用簡(jiǎn)單的a = b就會(huì)把同一個(gè)列表指向a受裹，這是我們不想看到的碌补。
此外，列表的添加項(xiàng)append棉饶，擴(kuò)展extend厦章，刪除項(xiàng)remove 等操作，都是在原列表上進(jìn)行的照藻，所以不能用賦值袜啃，否則會(huì)返回空None。而且幸缕，代碼里的這一段：
res = [num]
res.extend(l)
result.append(res)
如果想要（偷懶）簡(jiǎn)化成：
result.append([num].extend(l))
也會(huì)得到None群发，所以需要先創(chuàng)建結(jié)果子列表再添加。
