處理排列組合問題的通用算法
發表時間:2023-08-17 來源:明輝站整理相關軟件相關文章人氣:
[摘要]很多網友發貼詢問諸如:八皇后問題、彩票問題(從m中數中選擇n(m>=n)的組合)等,其實這都可歸結為排列組合的問題。解決這類問題,用for循環嵌套是不現實的(只能對指定的m、n編程,而且程序看...
很多網友發貼詢問諸如:八皇后問題、彩票問題(從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;
}