【試題描述】輸入一個(gè)字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc，則打印出a，b，c所能排列出來(lái)的所有字符串a(chǎn)bc，acb，bac，bca，cab，cba。

分析：這是一道很好的考查對(duì)遞歸理解的編程題，因此在過(guò)去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。

我們以三個(gè)字符abc為例來(lái)分析一下求字符串排列的過(guò)程。首先我們固定第一個(gè)字符a，求后面兩個(gè)字符bc的排列。當(dāng)兩個(gè)字符bc的排列求好之后，我們把第一個(gè)字符a和后面的b交換，得到bac，接著我們固定第一個(gè)字符b，求后面兩個(gè)字符ac的排列?，F(xiàn)在是把c放到第一位置的時(shí)候了。記住前面我們已經(jīng)把原先的第一個(gè)字符a和后面的b做了交換，為了保證這次c仍然是和原先處在第一位置的a交換，我們?cè)谀胏和第一個(gè)字符交換之前，先要把b和a交換回來(lái)。在交換b和a之后，再拿c和處在第一位置的a進(jìn)行交換，得到cba。我們?cè)俅喂潭ǖ谝粋€(gè)字符c，求后面兩個(gè)字符b、a的排列。

既然我們已經(jīng)知道怎么求三個(gè)字符的排列，那么固定第一個(gè)字符之后求后面兩個(gè)字符的排列，就是典型的遞歸思路了。

為方便起見(jiàn)，用123來(lái)示例下。123的全排列有123、132、213、231、312、321這六種。首先考慮213和321這二個(gè)數(shù)是如何得出的。顯然這二個(gè)都是123中的1與后面兩數(shù)交換得到的。然后可以將123的第二個(gè)數(shù)和每三個(gè)數(shù)交換得到132。同理可以根據(jù)213和321來(lái)得231和312。因此可以知道——全排列就是從第一個(gè)數(shù)字起每個(gè)數(shù)分別與它后面的數(shù)字交換。找到這個(gè)規(guī)律后，遞歸的代碼就很容易寫出來(lái)了：

對(duì)于一個(gè)n 位的字符串來(lái)講，它是n-1位字符串的排列 加上 沒(méi)有在 n -1 位字符串里 那個(gè)字符 的排列。 有點(diǎn)難理解，用例子說(shuō)明：對(duì)于字符串ABC來(lái)講，它所有的排列就是 A + BC 的排列 加上 B + AC 的排列，再加上 C + AB的排列。而B(niǎo)C的排列是 B + C 的排列 加上 C + B 的排列。所以，對(duì)一個(gè)字符串，我們從中去一個(gè)值，然后求剩余部分的排列，然后把它們?cè)俳M合在一起。所有，代碼如下

【參考代碼】

如果字符串中有重復(fù)字符的話，這個(gè)方法肯定不會(huì)符合要求的

1 public static void permutation(char[] arr, int begin) 2 { 3 // if pBegin points to the end of string, 4 // this round of permutation is finished, 5 // print the permuted string 6 7 if (begin == arr.length) 8 System.out.println(Arrays.toString(arr)); 9 else 10 { 11 for (int i = begin; i < arr.length; i++) 12 { 13 swap(arr, i, begin); 14 permutation(arr, begin + 1); 15 // restore pCh and pBegin 16 // PS:改變字符串順序后必須還原回來(lái)！ 17 swap(arr, i, begin); 18 } 19 } 20 } 21 22 public static void swap(char[] arr, int i, int j) 23 { 24 char temp = arr[i]; 25 arr[i] = arr[j]; 26 arr[j] = temp; 27 }

二、去掉重復(fù)的全排列的遞歸實(shí)現(xiàn)

由于全排列就是從第一個(gè)數(shù)字起每個(gè)數(shù)分別與它后面的數(shù)字交換。我們先嘗試加個(gè)這樣的判斷——如果一個(gè)數(shù)與后面的數(shù)字相同那么這二個(gè)數(shù)就不交換了。如122，第一個(gè)數(shù)與后面交換得212、221。然后122中第二數(shù)就不用與第三個(gè)數(shù)交換了，但對(duì)212，它第二個(gè)數(shù)與第三個(gè)數(shù)是不相同的，交換之后得到221。與由122中第一個(gè)數(shù)與第三個(gè)數(shù)交換所得的221重復(fù)了。所以這個(gè)方法不行。

換種思維，對(duì)122，第一個(gè)數(shù)1與第二個(gè)數(shù)2交換得到212，然后考慮第一個(gè)數(shù)1與第三個(gè)數(shù)2交換，此時(shí)由于第三個(gè)數(shù)等于第二個(gè)數(shù)，所以第一個(gè)數(shù)不再與第三個(gè)數(shù)交換。再考慮212，它的第二個(gè)數(shù)與第三個(gè)數(shù)交換可以得到解決221。此時(shí)全排列生成完畢。
這樣我們也得到了在全排列中去掉重復(fù)的規(guī)則——去重的全排列就是從第一個(gè)數(shù)字起每個(gè)數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換。

1 // 在[nBegin,nEnd)區(qū)間中是否有字符與下標(biāo)為pEnd的字符相等 2 static boolean isSwap(char[] arr ,int pBegin, int pEnd) 3 { 4 int p; 5 for (p = pBegin; p < pEnd; p++) 6 { 7 if (arr[p] == arr[pEnd]) 8 return false; 9 } 10 return true; 11 } 12 13 public static void permutation2(char[] arr, int begin) 14 { 15 // if pBegin points to the end of string, 16 // this round of permutation is finished, 17 // print the permuted string 18 if (begin == arr.length) 19 System.out.println(Arrays.toString(arr)); 20 21 else 22 { 23 for (int i = begin; i < arr.length; i++) 24 { 25 if (isSwap(arr,begin, i)) 26 { 27 swap(arr, begin, i); 28 permutation(arr, begin + 1); 29 // restore pCh and pBegin 30 // PS:改變字符串順序后必須還原回來(lái)！ 31 swap(arr, begin, i); 32 } 33 } 34 } 35 }

?三、全排列的非遞歸實(shí)現(xiàn)
??? 要考慮全排列的非遞歸實(shí)現(xiàn)，先來(lái)考慮如何計(jì)算字符串的下一個(gè)排列。如"1234"的下一個(gè)排列就是"1243"。只要對(duì)字符串反復(fù)求出下一個(gè)排列，全排列的也就迎刃而解了。
如何計(jì)算字符串的下一個(gè)排列了？來(lái)考慮"926520"這個(gè)字符串，我們從后向前找第一雙相鄰的遞增數(shù)字，"20"、"52"都是非遞增的，"26 "即滿足要求，稱前一個(gè)數(shù)字2為替換數(shù)，替換數(shù)的下標(biāo)稱為替換點(diǎn)，再?gòu)暮竺嬲乙粋€(gè)比替換數(shù)大的最小數(shù)（這個(gè)數(shù)必然存在），0、2都不行，5可以，將5和2交換得到"956220"，然后再將替換點(diǎn)后的字符串"6220"顛倒即得到"950226"。
對(duì)于像“4321”這種已經(jīng)是最“大”的排列，采用STL中的處理方法，將字符串整個(gè)顛倒得到最“小”的排列"1234"并返回false。

這樣，只要一個(gè)循環(huán)再加上計(jì)算字符串下一個(gè)排列的函數(shù)就可以輕松的實(shí)現(xiàn)非遞歸的全排列算法。按上面思路并參考STL中的實(shí)現(xiàn)源碼，不難寫成一份質(zhì)量較高的代碼。值得注意的是在循環(huán)前要對(duì)字符串排序下，可以自己寫快速排序的代碼

轉(zhuǎn)：http://blog.csdn.net/zz198808/article/details/7657168

總結(jié):
1、全排列就是從第一個(gè)數(shù)字起每個(gè)數(shù)分別與它后面的數(shù)字交換。
2、去重的全排列就是從第一個(gè)數(shù)字起每個(gè)數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換。
3、全排列的非遞歸就是由后向前找替換數(shù)和替換點(diǎn)，然后由后向前找第一個(gè)比替換數(shù)大的數(shù)與替換數(shù)交換，最后顛倒替換點(diǎn)后的所有數(shù)據(jù)。

?

字符串全排列擴(kuò)展----八皇后問(wèn)題
??? 題目：在8×8的國(guó)際象棋上擺放八個(gè)皇后，使其不能相互攻擊，即任意兩個(gè)皇后不得處在同一行、同一列或者同一對(duì)角斜線上。下圖中的每個(gè)黑色格子表示一個(gè)皇后，這就是一種符合條件的擺放方法。請(qǐng)求出總共有多少種擺法。

?

?

??? 這就是有名的八皇后問(wèn)題。解決這個(gè)問(wèn)題通常需要用遞歸，而遞歸對(duì)編程能力的要求比較高。因此有不少面試官青睞這個(gè)題目，用來(lái)考察應(yīng)聘者的分析復(fù)雜問(wèn)題的能力以及編程的能力。

由于八個(gè)皇后的任意兩個(gè)不能處在同一行，那么這肯定是每一個(gè)皇后占據(jù)一行。于是我們可以定義一個(gè)數(shù)組ColumnIndex[8]，數(shù)組中第i個(gè)數(shù)字表示位于第i行的皇后的列號(hào)。先把ColumnIndex的八個(gè)數(shù)字分別用0-7初始化，接下來(lái)我們要做的事情就是對(duì)數(shù)組ColumnIndex做全排列。由于我們是用不同的數(shù)字初始化數(shù)組中的數(shù)字，因此任意兩個(gè)皇后肯定不同列。我們只需要判斷得到的每一個(gè)排列對(duì)應(yīng)的八個(gè)皇后是不是在同一對(duì)角斜線上，也就是數(shù)組的兩個(gè)下標(biāo)i和j，是不是i-j==ColumnIndex[i]-Column[j]或者j-i==ColumnIndex[i]-ColumnIndex[j]。

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/WayneZeng/archive/2013/04/09/3011233.html

總結(jié)

以上是生活随笔為你收集整理的【IT笔试面试题整理】字符串的排列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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