解决排列组合问题的通用算法
【打印文章】
很多网友发贴询问诸如:八皇后问题、彩票问题(从m中数中选择n(m>=n)的组合)等,其实这都可归结为排列组合的问题。解决这类问题,用for循环嵌套是不现实的(只能对指定的m、n编程,而且程序看上去异常繁琐),较好的方法是回朔法。下面给出这类问题的一般算法的c/c++描述:
int combine(int a[],int sub){
//a[1..?]表示候选集,sub表示一个排列(组合)的元素个数
{
int total=sizeof(a);
int order[sub+1];
int count=0;//符合条件的排列(组合)的个数
order[0]=-1;
for(int i=1;i<=sub;i++)
order[i]=i;
int k=sub;
bool flag=true;
while(order[0]!=-1){
if(flag){
for(i=1;i<=sub;i++)//输出符合要求的组合
printf("%d ",a[order[i]]);
printf("\n");
count++;
flag=false;
}
order[k]++;
if(order[k]==total+1){
order[k--]=0;
continue;
}
...
//在此加入order[k]的限制条件
//如果条件满足,则往下执行
//否则continue;
if(k<sub){
order[++k]=order[k-1];
continue;
}
if(k==sub)
flag=true;
}
return count;
}
int combine(int a[],int sub){
//a[1..?]表示候选集,sub表示一个排列(组合)的元素个数
{
int total=sizeof(a);
int order[sub+1];
int count=0;//符合条件的排列(组合)的个数
order[0]=-1;
for(int i=1;i<=sub;i++)
order[i]=i;
int k=sub;
bool flag=true;
while(order[0]!=-1){
if(flag){
for(i=1;i<=sub;i++)//输出符合要求的组合
printf("%d ",a[order[i]]);
printf("\n");
count++;
flag=false;
}
order[k]++;
if(order[k]==total+1){
order[k--]=0;
continue;
}
...
//在此加入order[k]的限制条件
//如果条件满足,则往下执行
//否则continue;
if(k<sub){
order[++k]=order[k-1];
continue;
}
if(k==sub)
flag=true;
}
return count;
}
本栏文章均来自于互联网,版权归原作者和各发布网站所有,本站收集这些文章仅供学习参考之用。任何人都不能将这些文章用于商业或者其他目的。( Pfan.cn )
【编程爱好者论坛】