全排列算法

我有一個比較好的全排列算法，我驗證了3、4、5的結果是正確的。

程序中沒有使用遞歸，只是幾個循環，速度還令人滿意。
在C466A，Win2000的機器上，進行8個數字的全排列，結果不顯示，重定向到一個文本文件中，耗時不到一秒鐘

。9個數字的全排列耗時6秒種。10個數字的全排列55秒種。（以上都不顯示結果，均重定向到一個文本文件）

11個數字的全排列（不顯示結果，在原程序中不定義ISPRINT）耗時大約16秒鐘。

。

歡迎各位指點

算法為：用兩個數組，一個數組存放當前結果，第二個數組是每一個數是否已經使用的標志。比如對10個數進

行全排列，第一個結果是：0 1 2 3 4 5 6 7 8 9。
然后把每一個數的使用標志均置為1。
然后開始主循環：
   先打印當前的結果。
   在前一個得到的結果中，從后往前找第一個由小到大排列的數。每找一次均置當前位上的數字的使用標志

為0，然后找第一個比這個數大但是沒有使用過的數。
比如前一個結果是：4 1 9 7 8 2 5 0 6 3，那么從后往前第一個由小到大排列的數是0，第一個比0大但是沒有

使用過的數是3（因為比0大的數字里只有6和3）。最后由小到大依次打印剩余沒有使用過的數字。所以下一個

結果是4 1 9 7 8 2 5 3 0 6。

源程序為（在BC++3.0下編譯成功）：

#include<stdio.h>/*這兩個庫函數是習慣性的加上去的^_^。*/
#include<stdlib.h>

#define ISPRINT/*是否打印結果的標志*/
#define MAX 200/*最大的數*/

unsigned int *_NUM;/*用于存放一條結果的數組指針*/
char *_NUMFLAG;/*用于存放是否已經使用的標志*/

#define NUM(j) (*(_NUM+(j)))/*第j位的數字*/
#define NUMFLAG(j) (*(_NUMFLAG+(j)))/*數字j是否已經使用的標志,0為沒有使用，1為已經使用*/
#define NUMUSE(j) (*(_NUMFLAG+(*(_NUM+(j)))))/*第j位上的數字是否已經使用的標志,0為沒有使用，1為已

經使用*/

void main()
{
unsigned int number,j;
int i;
printf("Input number=");scanf("%u",&number);
if((number>=MAX)||(number<=1)){puts("輸入數據錯誤。");exit(-1);}

/*初始化內存和第一個結果*/
_NUM=(unsigned int*)malloc(sizeof(unsigned int)*number);
if(!_NUM){puts("分配給_NUM出現內存不足");exit(-1);}
_NUMFLAG=(char*)malloc(sizeof(char)*number);
if(!_NUMFLAG){puts("分配給_NUMFLAG出現內存不足");exit(-1);}

for(i=0;i<number;i++)NUM(i)=i,NUMFLAG(i)=1;/*初始化第一條結果和使用標志*/

do{/*主循環*/
 
 #ifdef ISPRINT/*打印結果*/
 for(j=0;j<number;j++)printf("%d ",NUM(j));/*打印一條結果。*/
 puts("");/*并換行*/
 #endif  

 NUMUSE(number-1)=0;//置最后一位數字的使用標志為0.

 /*在前一個結果中從后往前尋找第一個從小到大排列的數，并存放到變量j中*/
 for(i=number-2;i>=0;i--){
  NUMUSE(i)=0;
  if(NUM(i)<NUM(i+1))break;
 }

 if(i<0)break;/*從這里退出主循環.*/

 for(j=NUM(i)+1;j<number;j++){
  if(!NUMFLAG(j))break;
 }

 NUMFLAG(j)=1;
 NUM(i)=j;

 for(j=0,i++;i<number;j++)
  if(!NUMFLAG(j))NUM(i++)=j,NUMFLAG(j)=1;
}while(1);
/*釋放內存*/
free(_NUM);
free(_NUMFLAG);
}

/*程序結束*/

當然了這個程序的速度并不是最快的，程序中還有很大的優化余地，還可以減少一些循環，或者采用其他更好的算法。

下載源程序http://263.csdn.net/FileBBS/files/2001_8/T_387_1.zip