解決排列組合問題的通用算法 
（加入日期:2003-5-3 點(diǎn)擊數(shù):6608）
【對(duì)此文發(fā)表評(píng)論】 【編程愛好者論壇】 【保存文章至硬盤】 【打印文章】 
 
很多網(wǎng)友發(fā)貼詢問諸如：八皇后問題、彩票問題（從m中數(shù)中選擇n(m>=n)的組合）等，其實(shí)這都可歸結(jié)為排列組合的問題。解決這類問題，用for循環(huán)嵌套是不現(xiàn)實(shí)的（只能對(duì)指定的m、n編程，而且程序看上去異常繁瑣），較好的方法是回朔法。下面給出這類問題的一般算法的c/c++描述：

int combine(int a[],int sub){
//a[1..?]表示候選集,sub表示一個(gè)排列(組合)的元素個(gè)數(shù)
{
   int total=sizeof(a);
   int order[sub+1];
   int count=0;//符合條件的排列(組合)的個(gè)數(shù)
   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]的限制條件
      //如果條件滿足,則往下執(zhí)行
      //否則continue;
      if(k<sub){
         order[++k]=order[k-1];
         continue;
      }
      if(k==sub)
         flag=true;
   }
   return count;
}

本欄文章均來自于互聯(lián)網(wǎng)，版權(quán)歸原作者和各發(fā)布網(wǎng)站所有，本站收集這些文章僅供學(xué)習(xí)參考之用。任何人都不能將這些文章用于商業(yè)或者其他目的。( ProgramFan.Com )