程序員必備演算法，排列組合
還記得排列組合嗎？
在高中的時候最常接觸的莫過於排列組合了，畢竟高考必考的嘛。我們先來回憶下這兩個的公式是啥：
排列組合公式
如果看到這個還有一丟丟的印象，說明大家的基礎都還不錯。那麼問題來了，大家都是學計算機的，我們如何用程序去模擬這個過程，從而達到列出所有排列組合的可能呢？
推薦下我的前端群：524262608，不管你是小白還是大牛，小編我都挺歡迎，不定期分享乾貨，包括我自己整理的一份2017最新的前端資料和零基礎入門教程，歡迎初學和進階中的小夥伴。
全排列的實現
暴力求解（不可取，不可取）
相信很多初入門的小夥伴首先想到的就是就是直接通過嵌套多個for循環去遍歷不就好了，只要不相等就直接輸出，就像下面這樣：
Advertisements
def force(): data = "abc"for i in range(len(data)): for j in range(len(data)): for k in range(len(data)): if data[i] != data[j] and data[j] != data[k] and data[k] != data[i]:print(data[i],data[j],data[k])if __name__ == '__main__':force()
看上去還可以的樣子，不過這樣有幾個壞處，如果不想全排列 abc 了，而是想對 abcd 進行全排列了，那麼我們必須要修改源代碼增加一個for循環，而且如果排列的數很多的話，那這個循環也太多了吧。
Advertisements
遞歸求解
上面這種解法實在有點不優雅，那麼我們如何在不修改源碼的情況下就可以求出所有的排列組合情況呢？我們先來看張圖：
解決全排列的重複問題
細心的小夥伴肯定會發現，上面的代碼其實是有問題的，如果排列的數組中有重複的元素那麼結果中也會有重複的排列，這是我們不希望看到的。那麼我們如何解決這個問題呢？
要想解決這個問題，我們首先需要知道這個問題是怎麼來的，還是參考剛剛的圖，我們稍微修改下：
這裡寫圖片描述
對於
abc的排列，當我們進行排列時，可以先考慮第1位可能有哪些情況，如上圖所示有a,b,c三種情況，然後再對後面的兩位進行排列，採用相同的思路，所以我們可以很容易的就通過遞歸實現全排列了。def rank(data, step): if len(data) == step+1:print(data) returnelse: for i in range(step, len(data)): data[step], data[i] = data[i], data[step] //讓當前首位依次為後面的每一個數rank(data, step + 1) //遞歸後面的情況data[step], data[i] = data[i], data[step]if __name__ == '__main__': data = list("abc")rank(data, 0)運行上面的代碼，可以得到和上面暴力求解一毛一樣的結果，且這次如果需要對其他情況進行全排列不需要再修改源代碼，且只用了一個循環（雖然用遞歸效率還不如多個循環^-^），不過至少代碼看上去還是很優雅的。
就拿 cac 這個舉個栗子：
當以第一個c為開頭時，我們需要對 ac 進行全排列，沒問題
當以a為開頭時，我們需要對 cc 進行全排列，沒問題
當以第二個c為開頭時，我們需要對 ca 進行全排列，這就有問題了，ac和ca的全排列不就一樣的嘛，而且開頭也一樣，這個肯定就會有重複了呀，我們對源碼稍加修改下：
def is_equal(data,left,right): #判斷left到當前right是否有相等的，如果有說明之前已經對這for i in range(left,right): #個進行過全排序了if data[i] == data[right]: return Truereturn Falsedef rank(data, step):if len(data) == step+1:print(data) returnelse: for i in range(step, len(data)): if is_equal(data,step,i): #加一個判斷continueelse:data[step], data[i] = data[i], data[step]rank(data, step + 1)data[step], data[i] = data[i], data[step]if __name__ == '__main__':data = list("bcc")rank(data, 0)ok，這樣運行上面的代碼的就不會有重複的問題了，這裡可能需要小夥伴們多思考下了，不過還是很簡單的。
組合問題
問題描述
加入我有一個數組
[1, 2, 3, 4, 5, 6]，我想從裡面隨機選出三個來，問有哪些取法。解決思路
同樣是遞歸，因為我們也不知道循環的具體次數嘛，但是要如何遞歸呢？
這裡寫圖片描述
不要急，假設我們要從上面的數組中選出3個元素出來。
我們首先從第一個元素下手，對於第一個元素，我們有兩個選擇：要 or 不要。
如果要了，那麼我們需要選擇的元素就少了一個了，我們只需要從後面的元素中選出兩個就夠了。
如果不要，我們就從第二個元素繼續看，此時我們還是要選出三個（本來想畫圖演示的，不過這個圖好像有點複雜，筆者畫圖實在是個菜鳥就偷會懶了）。
推薦下我的前端群：524262608，不管你是小白還是大牛，小編我都挺歡迎，不定期分享乾貨，包括我自己整理的一份2017最新的前端資料和零基礎入門教程，歡迎初學和進階中的小夥伴。
def combine(data, step, select_data, target_num):if len(select_data) == target_num: #選擇的元素已經夠了，就輸出並返回print(select_data) returnif step >= len(data): #沒有元素選了而且還沒夠，也是直接返回returnselect_data.append(data[step]) #選擇當前元素combine(data, step + 1, select_data, target_num)select_data.pop() #別忘了從已選擇元素中先刪除combine(data, step + 1, select_data, target_num) #不選擇當前元素if __name__ == '__main__':data = [1, 2, 3, 4, 5, 6]combine(data, 0, [], 3)
運行上面的代碼就可以得出所有的組合可能了，還是比較優雅的。但是同樣當數組中有重複元素的時候也會有重複的組合，這個如何解決呢？這個就讓小夥伴們自己思考下吧。
總結
排列組合演算法還是很貼近我們生活的，在各種演算法，項目與面試中也會經常遇見，所以也算程序員必備演算法了，上面代碼如果有問題也歡迎小夥伴與筆者留言私信交流，一起學習交流一起進步。