字符串的全排列

• 題目：輸入一個字符串，打印出改字符串中所有字符的所有排列。例如輸入字符串a(chǎn)bc，那么打印出由a，b，c字符組成的所有字符串：abc，acb，bac，bca，cab，cba

• 如何求解全排列，這個問題初看還是比較復(fù)雜的，在之前的文章 ：數(shù)據(jù)結(jié)構(gòu)與算法–代碼完整性案例分析中我們在解決問題 “打印1 到最大的n位數(shù)” 的時候也用了全排列的方式是解決，思路是將1~n 位看成獨(dú)立的一位，然后每一位都可能是 0 ~ 9 的組合，這樣遞歸去排列每一位。

• 借鑒上文中的這題的思路進(jìn)行全排列看似能找到解決方案，但是此處又有所不同，因為上文中全排列是按位來枚舉，此處不行，不能重復(fù)，例如，abc無法出現(xiàn) aaa的排列字符串。

• 分析

  • 借鑒之前文章中的全排列思想，我們還是逐個字符串分析
  • 將字符串看成是兩部分組成，第一部分是第一個字符，第二部分是后面所有字符串。

• 觀察如上案例，我們看到，我們固定第一個字符，然后求后面字符的全排列

• 接著，我們固定后面字符的第一個字符，再求后面字符的全排列，依次類推，這個步驟我們可以通過遞歸來實(shí)現(xiàn)

• 在觀察看，以上三種情況，第一個將a與第一個字符交換得，第二個將a與第二個字符交換，三個將a與第三個字符交換

• 得到結(jié)論，當(dāng)固定第一個字符時候，我們將第一個字符分別與后面的n個字符分別交換，得到第一個字符的全排列，

• 接著固定第一個字符，從第二個字符開始，求第二個字符的全排列，這樣就避免了出現(xiàn)aaa的情況，并且也可以通過遞歸去解決此問題

• 通過如上分析，有如下代碼：

/*** 求字符串的全排列** @author liaojiamin* @Date:Created in 12:07 2021/5/24*/ public class Permutation {public static void main(String[] args) {permutationArray("ertgf");}public static void permutationArray(String arr) {char[] pChars = arr.toCharArray();permutationArray(pChars, 0);}public static void permutationArray(char[] pChars, Integer start){if(pChars == null || pChars.length <= 1 || start == pChars.length - 1){printArray(pChars);}for (int i = start;i<=pChars.length-1;i++){char temp = pChars[i];pChars[i] = pChars[start];pChars[start] = temp;permutationArray(pChars, start +1);temp = pChars[i];pChars[i] = pChars[start];pChars[start] = temp;}}public static void printArray(char[] pChars){if(pChars == null || pChars.length <= 1){return;}for (char pChar : pChars) {System.out.print(pChar+",");}System.out.println();} }

字符串組合

• 以上我們解決了字符串的全排列問題，如果我們需要得到字符串的所有組合應(yīng)該怎么辦？

• 還是輸入三個字符a，b，c，那么會有如下組合a,b,c,ab,ac,bc,abc

• 如果我們安如上思路進(jìn)行交換雖然能得到不同的排列，但是得到的確實(shí)同一個組合，例如，ab和ba是不同的排列，但是只是一個組合。

• 我們將組合問題歸類如下數(shù)學(xué)描述：

  • 如果輸入n個字符，則這n個字符能構(gòu)成長度為 1 ~ n de zuhe
  • 在求解n個字符 的 長度為 m的組合（1<=m <=n）的組合時候我們還是同上面思路，將n個字符串分為兩部分第一個字符和其余所有字符
    • 如果第一個字符參與組合，則下一步在剩余 n-1個字符中挑選m - 1個
    • 如果第一個字符不參與組合，則下一步在剩余 n-1個字符中挑選m個

• 依次按如上邏輯執(zhí)行每一個位置的邏輯，直到 n 字符到達(dá)最后一個字符，或者，獲取到m個字符為止

• 根據(jù)如上分析有如下代碼：

public static void main(String[] args) {permutationArray("ertgf");combination("abcde".toCharArray());}public static void combination(char[] pChars){if(pChars == null){return;}Stack<Character> combinaChar = new Stack<>();for (Integer i = 1; i <= pChars.length; i++) {combination(pChars, 0, i, combinaChar);}}/*** 求解字符串的所有組合* */public static void combination(char[] pChars, Integer begin, Integer number, Stack<Character> combinaChar){if(number <= 0){System.out.println(combinaChar.toString());return;}if(begin == pChars.length){return;}//第一個字符放入組合中combinaChar.push(pChars[begin]);combination(pChars, begin +1, number-1, combinaChar);//第一個字符不放入組合中combinaChar.pop();combination(pChars, begin+1, number, combinaChar);}

上一篇：數(shù)據(jù)結(jié)構(gòu)與算法–二叉查找樹轉(zhuǎn)順序排列雙向鏈表
下一篇：數(shù)據(jù)結(jié)構(gòu)與算法-- 八皇后問題（兩種實(shí)現(xiàn)方案）

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法--字符串的排列组合问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。