1、字符串全排列算法(sun f)C語(yǔ)言實(shí)現(xiàn)問(wèn)題(wnt)描述：輸入(shr)一個(gè)字符串，打印出該字符串中字符的所有排列。輸入:123輸出:123132213231312321問(wèn)題分析：現(xiàn)象分析：這種問(wèn)題，從直觀感覺(jué)就是用遞歸方法來(lái)實(shí)現(xiàn)即：把復(fù)雜問(wèn)題逐漸簡(jiǎn)單化，進(jìn)而得出具體代碼實(shí)現(xiàn)。（如何發(fā)現(xiàn)一個(gè)問(wèn)題可以使用遞歸方式來(lái)解決？ 經(jīng)分析可以發(fā)現(xiàn)：M個(gè)數(shù)的排列方法與n(nm)個(gè)數(shù)的排列方法沒(méi)有區(qū)別，處理方法與數(shù)據(jù)的個(gè)數(shù)沒(méi)有關(guān)系。處理方法的一致性，就可以采用遞歸）。3個(gè)數(shù)（123）排列，第一位1不動(dòng)，剩下兩個(gè)數(shù)（23）的排列，只要相互顛倒一下，就可以出現(xiàn)關(guān)于1開(kāi)頭的所有排列 123 132把2換到第一位，

2、保持不動(dòng)，剩下的兩個(gè)數(shù)（13）的排列，只要相互顛倒一下，就可以出現(xiàn)關(guān)于2開(kāi)頭的所有排列 213 231同理，把3換到第一位，可得到 312 321擴(kuò)展：把3個(gè)數(shù)的所有排列，前面加一個(gè)4，就可以得到關(guān)于4開(kāi)頭的所有的排列412341324213423143124321若把4與后續(xù)數(shù)據(jù)中的任意一個(gè)數(shù)據(jù)交換，通過(guò)完成對(duì)后續(xù)三個(gè)數(shù)的全排列，就可以得到相應(yīng)的數(shù)開(kāi)頭的四數(shù)的排列。總結(jié)：對(duì)4個(gè)數(shù)的排列，可以轉(zhuǎn)換成首位不動(dòng)，完成對(duì)3個(gè)數(shù)的排列對(duì)3個(gè)數(shù)的排列，可以轉(zhuǎn)換成首位不動(dòng)，完成對(duì)2個(gè)數(shù)的排列對(duì)2個(gè)數(shù)的排列，可以轉(zhuǎn)換成首位不動(dòng)，完成對(duì)1個(gè)數(shù)的排列對(duì)于1個(gè)數(shù)，無(wú)排列，直接輸出結(jié)果算法(sun f)實(shí)現(xiàn)(shx

3、in)說(shuō)明(shumng)：對(duì)n個(gè)數(shù)的排列，分成兩步：（1）首位不動(dòng)，完成對(duì)n-1個(gè)數(shù)的排列，（2）循環(huán)將后續(xù)其他數(shù)換到首位，再次進(jìn)行n-1個(gè)數(shù)的排列注：排列完成后，最終的串要與原串相同C語(yǔ)言代碼實(shí)現(xiàn)： #include #include /將串左移一位，首位存到末尾。void shift( char *s )if ( !s|!s0 ) return ; /security code . null stringchar ch=s0;int i=0;while( s+i )si-1=si ;si-1=ch;/本函數(shù)對(duì)于一個(gè)已排序好的數(shù)據(jù)進(jìn)行全排列void permutation(char lis

4、t, int head ) int i,len; len=strlen(list) ; if ( len-head = 1 ) /后續(xù)沒(méi)有再排列的，則輸出排列數(shù)據(jù) printf( %sn, list ); else for (i = k; ilen; i+) /從當(dāng)前位置開(kāi)始，每個(gè)數(shù)當(dāng)一次隊(duì)首，并進(jìn)行后續(xù)排列 permutation(list, head+1); /后續(xù)串排列shift( &listhead ); /輪流為當(dāng)?shù)谝?void pailie( char *str ) permutation( str, 0 ); /排列(pili)算法，從串的第幾位開(kāi)始排列 int main() c

5、har str=1234; pailie(str); return 0;帶重復(fù)(chngf)數(shù)據(jù)的排列(pili)問(wèn)題：如果有重復(fù)數(shù)據(jù)出現(xiàn)在待排列的數(shù)據(jù)中，則，若某數(shù)已經(jīng)當(dāng)過(guò)隊(duì)首，則與其相同的數(shù)再當(dāng)隊(duì)首是一樣的排列結(jié)果，如：1233進(jìn)行全排列當(dāng)?shù)谝粋€(gè)3當(dāng)隊(duì)首時(shí)，會(huì)出現(xiàn)一次全排列第二個(gè)3當(dāng)隊(duì)首時(shí)，會(huì)出現(xiàn)與第一個(gè)3當(dāng)隊(duì)首相同的全排列，因此，只需要保證此數(shù)據(jù)出現(xiàn)過(guò)隊(duì)首時(shí)，不要讓其再當(dāng)隊(duì)首就可以解決問(wèn)題了。代碼實(shí)現(xiàn)：/檢查chk位的數(shù)據(jù)是否曾經(jīng)當(dāng)過(guò)隊(duì)首/*list:待排列的全部數(shù)據(jù) chk:待檢查的位置 begin:已當(dāng)過(guò)隊(duì)首的數(shù)據(jù)的起始位置。因?yàn)槭且莆?，所以，從begin檢查到list尾就可以了。*

6、/is_dup( char *list, int begin, int chk )int i;for( i=begin; listi; i+ )if ( listchk = listi )return 1;return 0;void permutation(char list, int k) int i,len; len=strlen(list) ; if ( len-k = 1 ) /后續(xù)沒(méi)有再排列的，則輸出排列數(shù)據(jù) printf( %sn, list ); else for (i = k; ibegin;i- )if ( send = si-1 )return 1;return 0;voi

7、d permutation(char list, int k) int i,len; len=strlen(list) ; if ( len-k = 1 ) /后續(xù)沒(méi)有再排列的，則輸出(shch)排列數(shù)據(jù) printf( %sn, list ); else for (i = k; ilen; i+) if ( !is_dup ( list,i,k ) ) /如果沒(méi)有重復(fù)(chngf)的，則進(jìn)行相應(yīng)的排列,否則(fuz)跳過(guò)之，因?yàn)椋合嗤臄?shù)據(jù)當(dāng)隊(duì)首，交換沒(méi)有意義swap(&listk, &listi);/交換permutation(list, k+1); /后續(xù)串排列swap(&listi, &listk);/恢復(fù) void pailie( char *str ) permutation( str, 0 ); /排列算法，從串的第幾位開(kāi)始排列 int main() char str=1234; pailie(str); return 0;內(nèi)容總結(jié)（1）字符串全排列算法C