隨筆 - 312, 文章 - 14, 評論 - 1393, 引用 - 0

          導航

          <2008年5月>
          27282930123
          45678910
          11121314151617
          18192021222324
          25262728293031
          1234567

          公告

          關注我的新浪微博

          我的著作









          常用鏈接

          留言簿(126)

          我參與的團隊

          隨筆分類(818)

          隨筆檔案(310)

          文章分類(1)

          文章檔案(8)

          相冊

          ADSL、3G查詢

          CSDN

          eclipse

          ibm

          Java EE

          Linux

          Web

          云服務

          代理網站

          關注的網站

          協議

          喜歡的Blog

          國內廣告平臺

          圖書出版

          在線培訓

          開發工具

          微博客戶端

          手機鈴聲

          操作系統

          • ReactOS
          • 一個與windowXP/2003兼容的操作系統

          數學

          文件格式

          源碼資源

          移動(Mobile)

          編程語言

          英語學習

          最新隨筆

          搜索

          •  

          積分與排名

          • 積分 - 1974565
          • 排名 - 6

          最新評論

          閱讀排行榜

          評論排行榜

          全排列算法原理和實現

          本文為原創,如需轉載,請注明作者和出處,謝謝!

          全排列是將一組數按一定順序進行排列,如果這組數有n個,那么全排列數為n!個。現以{1, 2, 3, 4, 5}為
          
          例說明如何編寫全排列的遞歸算法。
          1、首先看最后兩個數4, 5。 它們的全排列為4 5和5 4, 即以4開頭的5的全排列和以5開頭的4的全排列。
          由于一個數的全排列就是其本身,從而得到以上結果。
          2、再看后三個數3, 4, 5。它們的全排列為3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六組數。
          即以3開頭的和4,5的全排列的組合、以4開頭的和3,5的全排列的組合和以5開頭的和3,4的全排列的組合.
          從而可以推斷,設一組數p = {r1, r2, r3, ... ,rn}, 全排列為perm(p),pn = p - {rn}。
          因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)。當n = 1時perm(p} = r1。
          為了更容易理解,將整組數中的所有的數分別與第一個數交換,這樣就總是在處理后n-1個數的全排列。
          算法如下:

          #include <stdio.h>  

          int n = 0;  

          void swap(int *a, int *b) 
          {     
              
          int m;     
              m 
          = *a;     
              
          *= *b;     
              
          *= m; 
          }  
          void perm(int list[], int k, int m) 
          {     
              
          int i;     
              
          if(k > m)     
              {          
                  
          for(i = 0; i <= m; i++)             
                      printf(
          "%d ", list[i]);         
                  printf(
          "\n");         
                  n
          ++;     
              }     
              
          else     
              {         
                  
          for(i = k; i <= m; i++)         
                  {             
                      swap(
          &list[k], &list[i]);             
                      perm(list, k 
          + 1, m);             
                      swap(
          &list[k], &list[i]);         
                  }     
              } 

          int main() 
          {     
              
          int list[] = {12345};     
              perm(list, 
          04);     
              printf(
          "total:%d\n", n);     
              
          return 0

          誰有更高效的遞歸和非遞歸算法,請回貼。




          Android開發完全講義(第2版)(本書版權已輸出到臺灣)

          http://product.dangdang.com/product.aspx?product_id=22741502



          Android高薪之路:Android程序員面試寶典 http://book.360buy.com/10970314.html


          新浪微博:http://t.sina.com.cn/androidguy   昵稱:李寧_Lining

          posted on 2008-05-11 15:43 銀河使者 閱讀(7878) 評論(11)  編輯  收藏 所屬分類: algorithmC/C++ 原創

          評論

          # re: 全排列算法原理和實現  回復  更多評論   

          #include<cstdlib>
          #include<iostream>
          #define CHESSNUM 9
          using namespace std;
          /*********************************************************/
          void Rank_Chess(int m);
          int Change_Rank(int w);
          bool Down_Rank(int x);
          void Up_Rank(int m);
          void Show();
          /**********************************************************/
          static char num[CHESSNUM];
          static int counter[CHESSNUM];
          static int num_counter=0;
          /**********************************************************/
          int main(){
          for(int x=0;x<CHESSNUM;x++)
          num[x]='A'+x;
          Show();
          for(int y=0;y<CHESSNUM;y++)
          counter[y]=CHESSNUM-1;
          Rank_Chess(CHESSNUM);
          cout<<"\n\n\nAdd up to "<<num_counter<<" number."<<endl;
          cout<<"\t\t\t\t---By 翟夢華"<<endl;
          getchar();
          return 0;
          }
          /**********************************************************/
          void Rank_Chess(int m){
          while(1){
          if(m==2){char currency;
          currency=num[CHESSNUM-1];
          num[CHESSNUM-1]=num[CHESSNUM-2];
          num[CHESSNUM-2]=currency;
          Show();}
          if(!(Down_Rank(m))) Rank_Chess(m-1); //recursive function
          else {Change_Rank(m+1);break;}
          }
          }
          /**********************************************************/
          int Change_Rank(int w){
          if(w>CHESSNUM) return 0;
          if(counter[CHESSNUM-w]==CHESSNUM-w)
          {counter[CHESSNUM-w]=CHESSNUM-1;return 0;}
          {char currency;
          currency=num[CHESSNUM-w];
          num[CHESSNUM-w]=num[counter[CHESSNUM-w]];
          num[counter[CHESSNUM-w]]=currency;
          }
          Up_Rank(w-1);counter[CHESSNUM-w]--;
          return 0;
          }
          /**********************************************************/
          bool Down_Rank(int x){
          for(int i=CHESSNUM-2;i>CHESSNUM-x-1;i--)
          if(num[i+1]>num[i]) return false;
          return true;
          }
          /**********************************************************/
          void Up_Rank(int m){
          char alter[100];
          for(int i=0;i<m;i++)
          alter[i]=num[CHESSNUM-1-i];
          for(int j=0;j<m;j++)
          num[CHESSNUM-m+j]=alter[j];
          Show();
          }
          /**********************************************************/
          inline void Show(){
          for(int x=0;x<CHESSNUM;x++)
          cout<<num[x];
          cout<<" |\t";
          num_counter++;
          }



          這是我以前寫的,雖然長了點有點啰嗦,但我測試過了,對9位數排列比你的快了13s.不信你自己試試.但我得承認你的代碼寫得很棒!
          2008-07-26 18:36 | 翟夢華

          # re: 全排列算法原理和實現  回復  更多評論   

          哦,真是越看越慚愧,你的思路可要比我清晰多了。雖然大家用的都是遞歸之妙,但我寫的東西真是太不成體統了。原本自己只學過2個禮拜的C便自以為已得算法之精妙,奈何山外有山。。。
          2008-07-26 18:50 | 翟夢華

          # re: 全排列算法原理和實現  回復  更多評論   

          這是我的全排列 JAVA語言
          package net.emlog.fei;

          import java.util.Date;

          public class ListAll {

          /**
          * @param args
          */
          public static void main(String[] args) {

          ListAll a = new ListAll();
          String[] strings ={"a","d","c","d","e","f","g","h","i"};
          String[] stringtt=null; ;
          Date date = new Date(System.currentTimeMillis());
          System.out.println(date.toString());
          stringtt=a.returnAll(strings);
          Date date1 = new Date(System.currentTimeMillis());
          System.out.println(date1.toString());
          for(int i = 0; i < stringtt.length;i++){
          System.out.println(stringtt[i].toString());
          }
          }
          /**
          * 分析全排列 我們發現 其有這么一個規律 即此數的全排列為在其前一個數的前排列所得到的數據的N個位置加上本身。1這本身
          * 如2 21 12 為 returnAll(2) = returnAll(1)+n 和 n + returnAll(1)
          * 3 為 m 0 to 2 returnAll(3) = returnAll(2)[t].subString(0,m) + n + returnAll(2)[t].subString(m); t 0 to returnAll(2).length
          * 所以 如下所示即可。
          * 出于效率的考慮,我設置了兩個變量。這兩個變量如果根據題目要求可以不要,不過那樣效率會很低。
          * @param n
          * @return
          */
          private String[] returnAll(int n){
          int length = 1;
          for(int k = 1;k<=n;k++){
          length = length*k;
          }
          String[] strings = new String[length];
          if(n==1){
          strings[0]=new Integer(n).toString();
          }else{
          String[] preStrings = returnAll(n-1);
          String tmpString;
          for(int t = 0 ; t<preStrings.length;t++){//數字的全排列的原數據來自于上一個上的全排列數組。
          tmpString = preStrings[t];
          for (int m =0 ;m<n ;m++){//上一個全排列數組中的某個數據從第0個索引開始到結束分別插入此數字
          strings[t*n+m] = tmpString.substring(0, m)+ n +tmpString.substring(m);
          }
          }

          }

          return strings;
          }

          /**
          * 可以隨意編寫字符來組成全排列數組
          * @param x
          * @return
          */
          private String[] returnAll(String[] x){
          int length = 1;
          for(int k = 1;k<=x.length;k++){
          length = length*k;
          }
          if(x.length !=length/(x[0].length()+1)){

          }
          String[] strings = new String[length];
          if(x.length==1){
          strings[0]=x[0];
          }else{
          String[] preStrings = returnAll(splitStrings(x));
          String tmpString;
          for(int t = 0 ; t<preStrings.length;t++){//全排列的原數據來自于上一個上的全排列數組。
          tmpString = preStrings[t];
          for (int m =0 ;m<x.length ;m++){//上一個全排列數組中的某個數據從第0個索引開始到結束分別插入此數據
          strings[t*x.length+m] = tmpString.substring(0, m)+ x[x.length-1] +tmpString.substring(m);
          }
          }

          }

          return strings;
          }
          /**
          * 以犧牲時間來換空間
          * @param n
          * @return
          */
          private String[] returnAllInOne(int n){
          int length = 1;
          for(int k = 1;k<=n;k++){
          length = length*k;
          }
          String[] strings = new String[length];
          if(n==1){
          strings[0]=new Integer(n).toString();
          }else{
          // String[] preStrings = returnAll(n-1);
          // String tmpString;
          for(int t = 0 ; t<returnAll(n-1).length;t++){
          // tmpString = returnAll(n-1)[t];
          for (int m =0 ;m<n ;m++){
          strings[t*n+m] = returnAll(n-1)[t].substring(0, m)+ n +returnAll(n-1)[t].substring(m);
          }
          }

          }

          return strings;
          }
          /**
          * 非1.6版本,生成除去數組的最后一位的數組
          * @param strings
          * @return
          */

          private String[] splitStrings(String[] strings){
          if(strings.length==0){return null;}
          String[] tmpStrings = new String[strings.length-1];
          for(int i =0;i<strings.length-1;i++){
          tmpStrings[i]=strings[i].toString();
          }
          return tmpStrings;
          }


          }

          對于9位數的排列未打印用時1秒分左右。
          2008-07-31 14:46 | fei

          # re: 全排列算法原理和實現  回復  更多評論   

          #include<stdio.h>
          #include<string.h>
          #define MAX 100
          int count=0;

          void cr(int str[],int x,int y)
          {
          int i;
          for(i=y-1;i>=x;i--)
          str[i+1]=str[i];
          str[i+1]=y;
          if(x>y-1)
          str[x]=y;
          }

          void hf(int str[],int x,int n)
          {
          int i;
          for(i=x;i<n;i++)
          str[i]=str[i+1];
          }


          void qpl(int str[],int m,int n)
          {
          int i;
          if(m==n+1)
          {
          for(i=1;i<m;i++)
          printf("%d",str[i]);
          printf("\n");
          count++;
          return;
          }
          for(i=1;i<=m;i++)
          {
          cr(str,i,m);
          qpl(str,m+1,n);
          hf(str,i,m);
          }
          }

          void main()
          {
          int n,str[MAX];
          printf("請輸入需要全排列的數:");
          scanf("%d",&n);
          qpl(str,1,n);
          printf("%d",count);
          }
          對樓主的算法的另一種表述
          2009-05-04 14:33 | ~~

          # re: 全排列算法原理和實現  回復  更多評論   

          #include <iostream>

          using std::cout;
          using std::endl;

          void Print(int a[], int len, int n);

          void PrintFullSeq(int n)
          {
          int* arr = new int[n];
          for (int i=0; i<n; i++)
          {
          arr[i] = i+1;
          }
          Print(arr, n, n);
          delete []arr;
          }

          void Print(int a[],int len, int n)
          {
          if (len==1)
          {
          for (int j=n; j>0; j--)
          {
          cout << a[j-1] <<" ";
          }
          cout << endl;
          return;
          }
          for (int i=len-1; i>=0; i--)
          {
          int temp = a[i];
          a[i] = a[len-1];
          a[len-1] = temp;

          Print(a, len-1, n);

          temp = a[i];
          a[i] = a[len-1];
          a[len-1] = temp;
          }
          }
          跟你的很象,會不會更好理解些?
          2009-09-17 02:04 | mi

          # re: 全排列算法原理和實現  回復  更多評論   

          翟夢華同學認識錯誤,會c只是基礎,算法可以是獨立語言的一種思想,就像你會加減乘除,并不代表你會解物理題一樣
          2009-09-21 15:35 | 夏亮

          # re: 全排列算法原理和實現  回復  更多評論   

          mi同學的算法跟作者有什么不一樣嗎?
          2009-09-21 15:36 | 夏亮

          # re: 全排列算法原理和實現  回復  更多評論   

          看看這個,這是后來寫的,簡單點了.

          #include<iostream>

          void contrary(char w[],int i){
          for(int x=0;x<i/2;x++)
          {char z=w[x]; w[x]=w[i-1-x]; w[i-1-x]=z;}
          }

          void permutation(char w[],int z){
          if(z<2) return;
          permutation(w,z-1);
          contrary(w,z-1);
          for(int i=0;i<z-1;i++){
          for(int j=z-1;j>0;j--)
          {char z=w[j]; w[j]=w[j-1]; w[j-1]=z;}
          std::cout<<w;
          permutation(w,z-1);
          if(i<z-2) contrary(w,z-1);
          }
          }

          int main(){
          char w[]="ABCDE";
          permutation(w,5);
          system("pause");
          }

          我理解中算法就是算法嘛,就像數學本身是數學,不是微積分,線性代數的集合一樣.
          2010-04-30 23:12 | 翟夢華

          # re: 全排列算法原理和實現[未登錄]  回復  更多評論   

          你那個M傳來傳去的到底有什么用處啊
          2010-05-21 21:10 | 李哲

          # re: 全排列算法原理和實現  回復  更多評論   

          算法有些細節需要優化。

          比如 你用if(k > m) 如果 k>m 需要轉跳2此才可以返回函數

          還有交換2個數2次, 其實可以用局部變量來保存。

          還有就是 函數的參數傳遞~,可以考慮用全局函數保存指針

          #include <iostream>

          using namespace std;

          int s[]={1, 2, 3, 4, 5, 6, 7, 8, 9};
          const int N = sizeof(s)/sizeof(int);
          int num;

          void p(void);
          void fun(int i);

          int main(int argc, char *argv[])
          {
          fun(0);

          cout << num << endl;
          return 0;
          }

          inline void p(void)
          {
          for (int i=0; i < N; ++i)
          {
          cout << s[i] << " ";
          }

          cout << endl;
          }

          void fun(int i)
          {
          if (i == N)
          {
          // p();
          ++num;
          return;
          }

          for (int a=i; a < N; ++a)
          {
          int x = s[i];
          int y = s[a];

          s[i] = y;
          s[a] = x;
          fun(i+1);
          s[i] = x;
          s[a] = y;

          }

          }
          2010-08-10 21:50 | xk8

          # re: 全排列算法原理和實現  回復  更多評論   

          其實昨天上面這個,沒多少優化。

          今天有做了個 循環版的。。

          結果簡單的時間計算。

          排列9位,運行100次
          樓主的代碼 9秒左右
          翟夢華的代碼 7-8秒左右
          我的這個因為沒有用遞歸 只要3.5秒這樣

          #include <iostream>

          using namespace std;

          int s[] = {1,2,3,4,5,6,7,8,9};
          const int N = sizeof(s)/sizeof(int);
          int t[N];
          int num;
          void p(void);
          void f(void);
          void swap(int *a, int *b);

          int main(int argc, char *argv[])
          {

          for (int a=0; a < 100; ++a)
          f();

          cout << num << endl;
          return 0;
          }

          void f()
          {
          int a=0;

          while(a != -1)
          {
          if (a == N)
          {
          //p();
          a--;
          num++;
          }
          else
          {
          while (a+t[a] == N)
          {
          t[a] = 0;
          a--;
          }

          if (a != -1)
          {

          if (a != a+t[a])
          {
          swap(&s[a], &s[a+t[a]-1]);
          }

          swap(&s[a], &s[a+t[a]]);

          t[a]++;

          a++;
          }

          }
          }
          }

          void swap(int *a, int *b)
          {
          int tmp = *a;
          *a = *b;
          *b = tmp;
          }
          void p()
          {
          for (int i=0; i < N; ++i)
          {
          cout << s[i] << " ";
          }

          cout << endl;
          }


          2010-08-11 12:28 | 來著
          主站蜘蛛池模板: 舟曲县| 万盛区| 闽侯县| 土默特左旗| 炎陵县| 富裕县| 玛多县| 天等县| 泰安市| 平罗县| 桦南县| 黄梅县| 和政县| 宁武县| 明溪县| 大方县| 太保市| 广西| 河西区| 大田县| 临泉县| 瓦房店市| 樟树市| 临颍县| 余姚市| 垣曲县| 萨嘎县| 清新县| 杭州市| 华阴市| 萍乡市| 嘉定区| 盐池县| 资溪县| 砚山县| 涡阳县| 黑龙江省| 田东县| 阜康市| 芜湖市| 甘泉县|