//===================================================================
// 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 ;故數值法不宜處理大數量.
且要透過篩選, 所以速度會較 易位法 來的慢, 它特點是避開了遞迴的使用.
