实现组合的C++代码

April 23, 2013

这些代码,验证了实现组合的一个算法。较为高效。运作原理就是常说的用二进制标志位标示选取的数字。 代码部分应该已经实现了所需的各个子函数,但是这个只是demo,如需要使用,需要检测是否有完备性问题。 现在将代码贴在这里:

#include
using std::cout;
using std::cin;
using std::endl;
#include
using std::string;

string createHelperStr(int maxCount,int subCount);
string* combination(string str,int subCount);
string sortStrASC(string str);
void printCombination(string helperStr);

int Total[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
#define Total_Item_Num (20)
#define Need_Combination_Count (10)

int main(){
cout<<createHelperStr(Total_Item_Num,Need_Combination_Count)<<endl;
combination(createHelperStr(Total_Item_Num,Need_Combination_Count),Need_Combination_Count);
return 0;
}

string createHelperStr(int maxCount, int subCount){
string retStr("");
for(int i = 0;i < maxCount;++i){
if(i < subCount)
retStr += "1";
else
retStr += "0";
}
return retStr;
}

string* combination(string str,int subCount){
bool isend = false;
static int count = 0;
while(1){
for(int i = 0; i < str.length();++i){
size_t findResult = str.find("10",0);
if(findResult == string::npos){
isend = true;
break;
}else{
str.replace(findResult,2,"01");
str.replace(0,findResult,sortStrASC(str.substr(0,findResult)));
count++;
printCombination(str);
}
}
if(isend)
break;
}
cout<<"共有"<<count+1<<"种组合"<<endl;
return NULL;
}

string sortStrASC(string str){
string retStr("");
for(int i = 0; i < str.length();++i){
if(i == 0){
retStr.append(str.substr(0,1));
continue;
}
if(str[i] == '1')
retStr.insert(0,"1");
else
retStr.append("0");
}
return retStr;
}

void printCombination(string helperStr){
for(int i = 0; i < Total_Item_Num; ++i){
if('1' == helperStr[i])
cout<<Total[i]<<" ";
}
cout<<endl;
}

Comments