组合问题的一般C++解法

很多问题都可以归结为组合问题：即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;		}