遞歸實現Ann全排列的枚舉(基於Python)
- 2019 年 10 月 8 日
- 筆記
本文1118字；預計閱讀8分鐘；
在寫一些概率統計題的模擬時，經常需要把A(n,n)、C(n,m)的排列組合全部列出來，這裡記錄一下A(n,n)全排列全部遍歷的實現。根據概率論中的排列組合知識知道A(n,n)=n!=n*(n-1)…*1；最終結果的數量一共有n的階乘，例如對於集合{1,2,3},有6種全排列。
要枚舉出所有的排列結果，我們從n=1開始來看，集合{1}的全排列就是{1}，n=2時，有 {1,2} 和 {2,1} ，可以看成是2和1交換位置，然後對{1}進行全排列；對{1,2,3}，先2和1交換，得到{2}和{1,3}，對{1,3}採用和n=2的情況相同的處理，所以是可以遞歸的，於是採用遞歸來寫，遞歸終止條件可以用n=1，也可以在n=2的時候就交換然後返回，歸納一下是將每個元素放到餘下n-1個元素組成的隊列最前方，對剩餘元素進行遞歸全排列。用Python翻譯這一思路：
def perm(lst): #input:list, 一個字元串格式的元素列表 n=len(lst) if n<=1: return lst elif n==2: return [lst[0]+lst[1],lst[1]+lst[0]] #終止條件 kk=[] for i in range(n): nlst=lst[0:i]+lst[i+1:] #除lst[i]外的元素 c=perm(nlst) ss=[lst[i]+j for j in c] kk.extend(ss) #注意是extend不是append return kk
上面perm函數被遞歸調用了。輸出格式是一個一維的數組。測試：
s=perm(['1','2','3']) #perm(list('123'))print(s)#['123', '132', '213', '231', '312', '321']
看一篇文章發現leetcode上正好有一個全排列的題：
Given a collection of distinct integers, return all possible permutations.
Example: Input: [1,2,3] Output:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
簡單說就是給定一個沒有重複數字的序列，返回其所有可能的全排列。不過其輸入是一個整數數值列表，輸出期望是二維數組。
簡單改一下剛才寫的程式碼：
class Solution(object): def permute(self, nums): """ :type lst: List[int] :rtype: List[List[int]] """ n=len(nums) if n<=1: return [nums] elif n==2: return [[nums[0],nums[1]],[nums[1],nums[0]]] kk=[] for i in range(n): nlst=nums[0:i]+nums[i+1:] c=self.permute(nlst) ss=[] for j in c: w=[nums[i]] w.extend(j) ss.append(w) kk.extend(ss) return kk
通過了測試：
leetcode第46題提交結果
另外發現Python的庫itertools有很好用的輪子：permutations和product，列出全排列很方便：
from itertools import permutations print(list(permutations('1234')))
而且permutations支援兩個參數，例如permutations('ABCD', 2)得到AB AC AD BA BC BD CA CB CD DA DB DC，就是從ABCD中任選兩個排列，A(4,2)。官方文檔給出了permutations(iterable[, r])實現的等價程式碼，是很好的參考資料。
具體關於permutations和product，可以看官方文檔： itertools.permutations (https://docs.python.org/2/library/itertools.html#itertools.permutations)。
