知識+ 排列

//===================================================================
// 20090418 知識 +
// http://tw.knowledge.yahoo.com/question/question?qid=1009041810620
// 發問者 : http://tw.knowledge.yahoo.com/my/my?show=AB05027385
//===================================================================


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//------------------------------------------
int CheckShow(int n, int num, int* nn, int base) //篩選與顯示排列
{ // n:排列數值 num:排列數目 nn:不同數陣列  base:基底
 int i, j, s;
 int* mm = &nn[base]; //之前有配置多餘空間來做為暫存
 for(i=0; i<base; i++) mm[i] = nn[i]&0xFF; //複製一份不同數的數量陣列
 for(j=num, i=n, s=0; j>0; j--, s=s*base+i%base, i/=base) // 篩選迴圈
   if(mm[i%base]--==0) return 0; // 篩選失敗
 for(j=0, i=s; j<num; j++, i/=base) // 顯示排列
   printf( "%s%d", (j==0)?"\n":",", nn[i%base]>>8 );
 return 1;
}
//................
int ValuePerm(int *a, int num) // 數值法排列處理
{ // a:陣列 num:數量
 int i, j, max, base, count=0;
 int * nn = (int *)malloc(num*sizeof(int)*2); // 配置不同數陣列
 for(i=0, j=0; i<num; i++, j=0) //不同數陣列處理與統計
 {
   nn[i] = a[i]<<8; // 高位元組藏放數值
   while( j<i && a[i]!=a[j]) j++; //檢查重覆
   nn[j]++; // 數量統計
 }
 for(i=0, base=0; i<num; i++) // 以不同數的數量為基底(base)
   if ((nn[i]&0xFF)!=0) nn[base++]=nn[i]; // 緊湊不同數陣列
 for(i=1, max=base; i<num; i++) max*=base; // 基數最大值+1
 for(int n = 0; n<max; n++) // 數值處理排列 : 0~最大值(max-1)
   if (CheckShow(n, num, nn, base)) count++; //篩選成功計數
 free(nn); // 釋放配置空間
 return count; // 傳回排列數量
}
//------------------------------------------
void swap(int *x, int *y) // 交換
{
 int t=*x; *x=*y; *y=t;
}
//................
int permutation(int *a, int num, int n=0 ) // 易位法排列處理
{ // a:陣列 num:數量 n:位置
 static int count;
 int i, j;
 if(n==0) count=0;
 if(n+1==num) // 處理到末位--顯示
 {
   for(i=0; i<num; i++)
     printf( "%s%d", (i==0)?"\n":",", a[i]);
   return ++count;
 }
 for(i=n; i<num; i++)
 {
   for(j=n; j<i && a[i]!=a[j]; j++);
   if (j==i) // 若尚未處理過此數
   {
     swap( a+i, a+n ); // 交換(易位)
     permutation( a, num, n+1 ); // 後面繼續易位排列(遞迴)
     swap( a+i, a+n ); // 回復易位
   }
 }
 return count;
}
//------------------------------------------
int main() // 主程式
{
 clock_t start;

 int A[] = { 1, 2, 3, 4, 5, 6, 7 }; // 陣列A
 int B[] = { 1, 1, 1, 1, 2, 2, 3 }; // 陣列B

 int numA = sizeof(A)/sizeof(int); // A 數量
 int numB = sizeof(B)/sizeof(int); // B 數量

 start = clock();
 int Anum = ValuePerm(A, numA); // A 數值法排列處理
 printf( "\n 共 %d 種排列 費時:%f\n\n", Anum, (double)(clock()-start));

 start = clock();
 int Bnum = ValuePerm(B, numB); // B 數值法排列處理
 printf( "\n 共 %d 種排列 費時:%f\n\n", Bnum, (double)(clock()-start));

 start = clock();
 Anum = permutation(A, numA); // A 易位法排列處理
 printf( "\n 共 %d 種排列 費時:%f\n\n", Anum, (double)(clock()-start));

 start = clock();
 Bnum = permutation(B, numB); // B 易位法排列處理
 printf( "\n 共 %d 種排列 費時:%f\n\n", Bnum, (double)(clock()-start));

 return 0;
}
//------------------------------------------ 

.

這個程式應用了兩種排列方法 : 數值法 與 易位法

易位法的觀念是每一位置都替換為不同位置的不同內容,並用遞迴的方式逐一處理下一位置.

數值法則是不使用遞迴,而是將陣列內容處理成連續數值,由連續數值中進行篩選出符合的數值.
數值法會以等於或大於(取2冪可加快運算速度)陣列內不同內容的數量來當作連續數值基底,
因此所得的連續數值的上限值將是 (數值基底^陣列內容數量)-1 ;故數值法不宜處理大數量.
且要透過篩選, 所以速度會較 易位法 來的慢, 它特點是避開了遞迴的使用.