補充全排列算法C語言實現(xiàn)(共5頁)

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

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

3、in)說明(shumng)：對n個數(shù)的排列，分成兩步：（1）首位不動，完成對n-1個數(shù)的排列，（2）循環(huán)將后續(xù)其他數(shù)換到首位，再次進行n-1個數(shù)的排列注：排列完成后，最終的串要與原串相同C語言代碼實現(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ù)對于一個已排序好的數(shù)據(jù)進行全排列void permutation(char lis

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

5、har str=1234; pailie(str); return 0;帶重復(chngf)數(shù)據(jù)的排列(pili)問題：如果有重復數(shù)據(jù)出現(xiàn)在待排列的數(shù)據(jù)中，則，若某數(shù)已經(jīng)當過隊首，則與其相同的數(shù)再當隊首是一樣的排列結(jié)果，如：1233進行全排列當?shù)谝粋€3當隊首時，會出現(xiàn)一次全排列第二個3當隊首時，會出現(xiàn)與第一個3當隊首相同的全排列，因此，只需要保證此數(shù)據(jù)出現(xiàn)過隊首時，不要讓其再當隊首就可以解決問題了。代碼實現(xiàn)：/檢查chk位的數(shù)據(jù)是否曾經(jīng)當過隊首/*list:待排列的全部數(shù)據(jù) chk:待檢查的位置 begin:已當過隊首的數(shù)據(jù)的起始位置。因為是移位，所以，從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ù)沒有再排列的，則輸出排列數(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ù)沒有再排列的，則輸出(shch)排列數(shù)據(jù) printf( %sn, list ); else for (i = k; ilen; i+) if ( !is_dup ( list,i,k ) ) /如果沒有重復(chngf)的，則進行相應(yīng)的排列,否則(fuz)跳過之，因為：相同的數(shù)據(jù)當隊首，交換沒有意義swap(&listk, &listi);/交換permutation(list, k+1); /后續(xù)串排列swap(&listi, &listk);/恢復 void pailie( char *str ) permutation( str, 0 ); /排列算法，從串的第幾位開始排列 int main() char str=1234; pailie(str); return 0;內(nèi)容總結(jié)（1）字符串全排列算法C