很多問題都可以歸結為組合問題:即C(n,m)---從n個元素中取m個,保存所有組合情況。
組合問題與排列問題不應該混為一談,排列需要考慮所取元素的放置順序,而組合問題則不考慮。
STL中提供的next_permutation解決的是排列問題,而且是全排列問題,即n個元素取出所有元素進行排列。
本篇記錄一般性組合問題的C++實現。
1.對于m較小的情況(通常3以下)可以直接枚舉:
比如C(5,3)直接枚舉即三重循環:
for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ for(int k=j+1;k<n;k++){ cout<<data[i]<<" "<<data[j]<<" "<<data[k]<<endl; } } }2.對于m較大時,枚舉循環重數過大,可采用遞歸實現一般性的組合函數://組合問題C(n,m):n個元素中取m個,保存所有組合情況void combine(int data[],int n,int m,int temp[],const int M,vector<vector<int> > &vec_res){ for(int i=n; i>=m; i--) // 注意這里的循環范圍 { temp[m-1] = i - 1; if (m > 1) combine(data,i-1,m-1,temp,M,vec_res); else // m == 1, 輸出一個組合 { vector<int > vec_temp; for(int j=M-1; j>=0; j--){ vec_temp.push_back(data[temp[j]]); } vec_res.push_back(vec_temp); } }}網上的做法是直接打印結果,為方便使用,對其進行修改,加入結果集參數vec_res,作為二維動態數組的引用,存儲所有的組合情況,便于提取進一步處理。main中調用方法如下:vector<vector<int> > vec_res; int *data=new int[n]; int *temp=new int[m]; for(int i=0;i<n;i++){ data[i]=i+1;//測試數據為1...n } combine(data,n,m,temp,m,vec_res); for(auto temp:vec_res){ for(auto e:temp){ cout<<e<<" "; } cout<<endl; } 測試結果如圖:
為方便和排列問題比較,調用STL的排列算法,打印1,2,3序列的全排列輸出:
//對比全排列問題 sort(data,data+n); for(int i=0;i<n;i++) cout<<data[i]<<" "; while(next_permutation(data,data+n)){ for(int i=0;i<n;i++){ cout<<data[i]<<" "; } cout<<endl; }
新聞熱點
疑難解答
圖片精選