程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 算法——遞歸生成集合的所有組合

算法——遞歸生成集合的所有組合

編輯:C++入門知識

題目描述 輸入一個集合,需要生成該集合所能得出的所有組合。舉例說明:若輸入集合為{1,2} , 需要生成的組合有{1},{1, 2},{2} 。該題目與生成集合的全排列有很多相似之處,同樣也是一個很經典的問題。     解決思路    這裡我們利用遞歸的思想來實現該問題的解。   面對這樣一個問題,我們需要仔細分析。題目要求生成一個集合的所有組合,也就是需要生成集合裡的元素所能夠組成的所有組合。於是一個很明顯的思路就是要遍歷該集合。一提到遍歷集合,可以使用循環或者遞歸來實現。針對本問題,利用遞歸的思想是很方便的。   假設我們的集合為{1,2,3} ,我們從頭掃描集合的元素,第一個元素為1。對於這個元素,我們可以把他放到組合集中,然後在剩下的集合裡再去選擇;也可以不把他放到組合集中,在剩下的集合裡去選擇元素放到組合集中。一般化的,假設我們的集合有n個元素,要求m個元素的組合。我們掃描每一個元素,針對該元素,我們可以將其放到組合集中,然後在剩下的n-1個元素中再選擇m-1個元素;我們也可以不放該元素進集合,而直接從剩下的n-1個元素中選擇m個元素。這已經是非常清晰的遞歸的思想了,具體代碼如下。     代碼 [cpp]   void combination(char *src,int num, vector<char>& result)   {       if(num==0)       {           vector<char>::iterator iter=result.begin();           for(;iter<result.end();iter++)           {               printf("%c",*iter);           }           printf("\n");           return;       }       if(*src=='\0') return;       result.push_back(*src);       combination(src+1,num-1,result);       result.pop_back();       combination(src+1,num,result);   }      void all_sub_set(char *src)   {       assert(src);       if(!src) return;       int i=0;       int len=strlen(src);       vector<char> result;          for(i=1;i<=len;i++)       {           combination(src,i,result);       }   }       小結 遞歸生成集合的所有組合,是考驗一個程序員編程基本功的問題,有一些技巧性。本問題與Gray Code按序生成集合子集屬於同一個問題的不同實現方法,都是很經典的解題方法。  

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved