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

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

2、的排列，只要相互顛倒一下，就可以出現(xiàn)關于2開頭的所有排列213 231同理，把3換到第一位，可得到312 321擴展:把3個數(shù)的所有排列，前面加一個4,就可以得到關于4開頭的所有的排列4123 4132 4213 4231 4312 4321若把4與后續(xù)數(shù)據(jù)中的任意一個數(shù)據(jù)交換，通過完成對后續(xù)三個數(shù)的全排列，就可以得到相應的數(shù)開頭的四數(shù)的排列。總結:對4個數(shù)的排列,可以轉換成首位不動,完成對3個數(shù)的排列對3個數(shù)的排列,可以轉換成首位不動,完成對2個數(shù)的排列對2個數(shù)的排列,可以轉換成首位不動,完成對1個數(shù)的排列對于1個數(shù)，無排列，直接輸出結果算法實現(xiàn)說明:對n個數(shù)的排列，分成兩步:首位不動，完成

3、對n.1個數(shù)的排列,循環(huán)將后續(xù)其他數(shù)換到首位，再次進行n-1個數(shù)的排列注：排列完成后，最終的串要與原串相同C 語言代碼實現(xiàn)：#in elude #in elude 將串左移一位，首位存到末尾。void shift( char *s )if ( !s| I !s0 ) retu rn ; /security code . n ull st ri ngchar ch=s0;int i=0;while( s+i)si-1=si;si-1=ch;/本函數(shù)對于一個已排序好的數(shù)據(jù)進行全排列void P ermutati on( char list, i nt head ) int i,le n;len 二

4、 strle n(list);if( len-head = 1 ) /后續(xù)沒有再排列的，則輸出排列數(shù)據(jù)prin tf( sn”，list);for (i = k; ilen; i+) /從當前位置開始，每個數(shù)當一次隊首，并進行后續(xù)排列permutation(list, head+1); /后續(xù)串排列shift( &listhead ); /輪流為當?shù)谝籿oid pailie( char *str)permutation( str, 0 ); / int main()排列算法，從串的第幾位開始排列char str尸1234;pailie(str);return 0;帶重復數(shù)據(jù)的排列問題：如果有重

5、復數(shù)據(jù)出現(xiàn)在待排列的數(shù)據(jù)中，則，若某數(shù)已經(jīng)當過隊首，則與其 相同的數(shù)再當隊首是一樣的排列結果，如：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尾就可以了。*/ is_dup( char int begin, int chk )int i;for( i=begin; listi; i+

6、)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);elsefor (i = k; ibegin;i-)if ( send = si-1)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);for (i = k; ilen; i+)if ( !is_dup ( list,i,k ) ) /如果沒有重復的，則進行相應的排列，否則跳過之，因為：相同的數(shù)據(jù)當隊首，交換沒有意義swap(&listk, &listi);/交換permutation(list, k+1); /后續(xù)串排列恢復void