实现组合的C++代码

这些代码,验证了实现组合的一个算法。较为高效。运作原理就是常说的用二进制标志位标示选取的数字。 代码部分应该已经实现了所需的各个子函数,但是这个只是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;
}

本文遵守 CC-BY-NC-4.0 许可协议。

Creative Commons License

欢迎转载,转载需注明出处,且禁止用于商业目的。

上篇CocoaPods问题总结
下篇GNUstep编译.m文件并连接形成可执行文件