全排列算法

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

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

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

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

。

歡迎各位指點

算法為：用兩個數(shù)組，一個數(shù)組存放當(dāng)前結(jié)果，第二個數(shù)組是每一個數(shù)是否已經(jīng)使用的標(biāo)志。比如對10個數(shù)進

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

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

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

結(jié)果是4 1 9 7 8 2 5 3 0 6。

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

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

#define ISPRINT/*是否打印結(jié)果的標(biāo)志*/
#define MAX 200/*最大的數(shù)*/

unsigned int *_NUM;/*用于存放一條結(jié)果的數(shù)組指針*/
char *_NUMFLAG;/*用于存放是否已經(jīng)使用的標(biāo)志*/

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

經(jīng)使用*/

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

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

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

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

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

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

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

 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);
/*釋放內(nèi)存*/
free(_NUM);
free(_NUMFLAG);
}

/*程序結(jié)束*/

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

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