Combination and Permutation

CombinationPermutation.md

##Combination and Permutation

基于递归的思路

    #include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    void Combination_m(char* pStr, int m,vector<int> path, vector<vector<int> >& result)
    {
    	if(pStr == nullptr || (*pStr == '\0' && m != 0))
    	{
    		return;
    	}
    	if(m == 0)
    	{
    		result.push_back(path);
    		return;
    	}
    	//choose
    	path.push_back(*pStr);
    	Combination_m(pStr+1,m-1,path,result);
    	path.pop_back();
    	//not choose
    	Combination_m(pStr+1,m,path,result);
    }
    
    vector<vector<int> > Combination(char* pStr)
    {
    	vector<vector<int> > result;
    	if(pStr == nullptr || pStr == '\0')
    	{
    		return result;
    	}
    
    	for(int i = 1 ; i <= strlen(pStr) ; ++i)
    	{
    		vector<int> path;
    		Combination_m(pStr,i,path,result);
    	}
    	return result;
    }
    void Permutation(char* pStr, char* begin, vector<string>& result)
    {
    	if(*begin == '\0')
    	{
    		string t = pStr;
    		result.push_back(t);
    	}
    	else
    	{
    		for(char* pCh = begin; *pCh != '\0' ; pCh++)
    		{
    			//action
    			swap(*pCh,*begin);
    			Permutation(pStr,begin+1,result);
    			//resume
    			swap(*pCh,*begin);
    		}
    	}
    }
    vector<string> Permutation(char* pStr)
    {
    	vector<string> result;
    	if(pStr == nullptr)
    	{
    		return result;
    	}
    	Permutation(pStr, pStr,result);
    	return result;
    }
    int main()
    {
    	char test[10] = "abcd";
    	cout<<"Testing combination:"<<endl;
    	vector<vector<int> > result = Combination(test);
    	for(int i = 0; i < result.size() ; i++)
    	{
    		for(int j = 0 ; j < result[i].size() ; j++)
    		{
    			cout<<(char)result[i][j]<<" ";
    		}
    		cout<<endl;
    	}
    	cout<<"Testing permutation:"<<endl;
    	vector<string> result2 = Permutation(test);
    	for(int j = 0 ; j < result2.size() ; j++)
    	{
    		cout<<result2[j]<<" ";
    	}
    	cout<<endl;
    	system("pause");
    	return 0;
    }

Testing