解决排列组合问题的通用算法

很多网友发贴询问诸如：八皇后问题、彩票问题（从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;

}