【分享】三种“聪明”的全排列函数
在24点游戏编程过程中，在“全排列”方面偶有所得，在此与大家分享一下。第一种“聪明”的全排列函数
int quan_pai_lie(int a[ ],int n)
//这个俺前几年自编的全排列函数很有特色。功能如下
//int型数组 a[ ]（n个元素）既是入口参数,也是出口参数。
//进入时要求从大到小排列,如{5,4,3,2,1}。调用1次就变成
//{5,4,3,1,2},再调用就变成{5,4,2,3,1},依此类推。函数
//的返回值通常是1,表示还有未尽的排列;如果返回0,则表示
//给出的排列已经全了。于本例,就是到达{1,2,3,4,5}状态。
//如果初始状态为{1,2,4,5,3},调用后相继出现{1,2,4,3,5}
//{1,2,3,5,4}最终{1,2,3,4,5}。该函数还能正确对待重复
//元素: 设n=4,最初{5,5,5,1},调用后相继出现{5,5,1,5}、
//{5,1,5,5}最终定格在{1,5,5,5}。
//欲改变排序方向,请按末尾带////的行中的提示修改代码
{ //from 5,4,3,2,1 to 1,2,3,4,5
int i,j,k,temp,t;
for(k=n-1;k>0;k--)
if(a[k-1]>a[k])break; ////改为a[k-1]<a[k]
if(k==0)return 0;
temp=a[k-1];i=k;
for(j=k+1;j<n;j++)
if(temp>a[j]&&a[j]>a[i])i=j; ////两个">"都改为"<"
a[k-1]=a[i];a[i]=temp;
for(i=k;i<n-1;i++)
for(j=k;j<n-1+k-i;j++)
if(a[j+1]>a[j]) ////改为a[j+1]<a[j]
{t=a[j];a[j]=a[j+1];a[j+1]=t;}
return 1;
}
第二种“聪明”的全排列函数
这个全排列函数permutation()是专门为24点游戏设计，所以它
只能实现4个不同或部分相同元素的全排列。说它“聪明”是指它
能够正确处理雷同元素；而且不要求初始排序。模仿本函数,不难
写出处理5个或更多个元素的全排列代码。
void use2(void(*fun)( ),int a,int b,int c,int d)
{
fun(a,b,c,d);if(c-d)
fun(a,b,d,c);
}
void use6(void(*f)(),int a,int b,int c,int d)
{
use2(f,a,b,c,d);if(b-c)
use2(f,a,c,d,b);if(b-d)if(c-d)
use2(f,a,d,b,c);
}
void permutation(void(*f)(),int a,int b,int c,int d)
{
use6(f,a,b,c,d);if(a-b)
use6(f,b,c,d,a);if(a-c)if(b-c)
use6(f,c,d,a,b);if(a-d)if(b-d)if(c-d)
use6(f,d,a,b,c);
}
//下面的main(void)提示您怎样调用这个全排列函数
#include<stdio.h>
void print(int a,int b,int c,int d)
{
printf("%d%d%d%d\n",a,b,c,d);
}
int main(void)
{
permutation( print,1,2,3,2 );
return 0;
}
屏幕输出如下(vc6.0)
1232
1223
1322
2321
2312
2213
2231
2132
2123
3212
3221
3122
Press any key to continue
第三种“聪明”的全排列函数
全排列函数 use24 为24点游戏设计，也不要求初始排序。
能够实现4个不同、相同或部分相同元素的全排列。特别是
这个嵌套调用函数的层次感非常好。现在把它介绍给大家。
void use4(void(*fun)( ),int a,int b,int c,int d)
{ //第3层次 组内成员次序
fun(a,b, c,d);//甲组a先b后；乙组c先d后
if(c-d)
fun(a,b, d,c);//甲组a先b后；乙组d先c后
if(a-b)
fun(b,a, c,d);//甲组b先a后；乙组c先d后
if(a-b && c-d)
fun(b,a, d,c);//甲组b先a后；乙组d先c后
}
void use8(void(*f)(),int a,int b,int c,int d)
{ //第2层次 "组"的次序
use4(f, a,b, c,d);//ab为甲组、cd为乙组
if(a==c && b==d || a==d && b==c)return;
use4(f, c,d, a,b);//cd为甲组、ab为乙组
}
void use24(void(*f)(),int a,int b,int c,int d)
{ //第1层次 两两分组
use8(f, a,b, c,d);//ab一组、cd另一组
if(a-c && b-d)
{
use8(f, a,d, b,c);//ad一组、bc另一组
if(a-b && a-d && b-c && c-d)
use8(f, a,c, b,d);
}
else if(a-d && b-c)
{
use8(f, a,c, b,d);//ac一组、bd另一组
if(a-b && a-c && b-d && c-d)
use8(f, a,d, b,c);//ad一组、bc另一组
}
}
//下面的main(void)提示怎样调用全排列函数use24
#include<stdio.h>
void print(int a,int b,int c,int d)
{
printf("%d%d%d%d\n",a,b,c,d);
}
int main(void)
{
use24( print,1,2,2,2 );
return 0;
}
屏幕输出如下(vc6.0)
1222
2122
2212
2221
Press any key to continue
