457
Java實現全排列、組合算法
全排列
解法一：
輸入一串字符，然後對字符進行全排列，如“abc”,全排列結果為："abc","acb","bac","bca","cab","cba".
分析：從字符串中選擇一個作為第一個字符，然後對剩下的字符串進行全排列，如此遞歸下去，直到打印出全部排列。如："abc"：
1、選a作為第一個字符：”abc“，”acb“；
2、選b作為第一個字符：”bac“，”bca“；
3、選c作為第一個字符：”cab“，”cba“；
參考代碼如下：
遞歸實現全排列算法
解法二：
這種解法是將字符串從小大倒排序，以此得到整體的最小順，然後找到次小順序，直到得到最大順序，也就是從大到小的順序，如：”23415“，最小順序是:"12345",次小順序是：”12354“，........直到最大順序：”54321“。這裏重點是找到某個順序值得下一個順序。找下一個順序的算法如下：假設到了”21543“，從後往前找到i-1位置小於i位置的下標，1<5,所以要找的下表pos=1，將下標為1的數字1,和它後麵最小的且大於它的數替換，”21543”--->"23541",然後再將下標1後麵的字符串翻轉得到："23145"，這就得到了“21543”下一個順序值“23145”，如此下去，直到輸出所有結果。如果你想學習java可以來這個群，首先是二二零，中間是一四二，最後是九零六，裏麵有大量的學習資料可以下載。
參考代碼如下：
排列算法的結果總共有n!個，所以時間複雜度至少n!級別。
組合算法
組合算法代碼比較簡單，可以讀代碼理解：
放回全排列
放回全排列就是類似於三個篩子總共有6*6*6=216中結果。使用遞歸思想解決，代碼比較簡潔。
參考代碼如下：
最後更新：2017-04-09 18:03:54