首页 > 代码库 > 求字符串中元素的所有组合

求字符串中元素的所有组合

       我们知道具有N个元素的数字进行组合,总共有2^N种情况。那么,如何用程序实现输出这些组合呢???这个问题似乎比 求N个元素进行全排列 的问题要复杂一些,大家可以动脑想一下或者动手去写写程序,那么该采取什么样的思路才是简单的呢???

       常规的思路我们会想到使用循环或者递归,但是实际动手操作起来非常复杂,经常会把自己绕晕,或者很难看懂别人写的程序。下面介绍一种使用不同思路实现的方法,简单有效:


       首先,把字符数组每一个元素用一个二进位表示,例如:


A B C D E
1 1 1 1 1 ---> 于是它最多有11111(二进制)种不重复组合(即31种)(不考虑顺序)


于是,只要检查从1到31这些数字的二进位哪些是二进制值1,就可以得出组合了。(位值为1的元素选取,位值为0的元素弃之)


函数getSubStr用于检查某整型数某二进位值是1还是0,如果是1则保留该位置的字符,为0则舍弃,最后将保留的字符组合返回。


#include <string>
#include <cmath>


string getSubStr(string str,int num)
{
	string tmp;
	int len=str.length();
	for(int i=0;i<len;++i)
	{
		if(num&0x1==1)//注意这里判断某位为0还是1的方法,与0x1相与,然后每次右移一位,再与0x1相与,外层循环同时会统计是哪位
			tmp.insert(0,str[len-i-1]);
		num=num>>1;
	}
	return tmp;
}
void getCombine(string str)
{


	int len=str.length();
	int Total=0;
	for(int i=0;i<len;++i)
	{
		Total+=pow(2,i);
	}
	string tmp;
	for(i=0;i<=Total;i++)
	{
		tmp=getSubStr(str,i);
		cout<<tmp<<endl;
	}
}
void main()
{
	string s="abcd";
	getCombine(s);
}

另外,目前递归版本还未调出,有大神可以提供下。


求字符串中元素的所有组合