两种求集合全部子集的方法

两种求集合全部子集的方法

大家好,又见面了,我是全栈君。

如果我们有一个求集合的所有子集(包括集合自身)的需求,即有一个集合s,包括两个元素 <a,b>,则其所有的子集为<a,ab,b>.

不难求得,子集个数sn与原集合元素个数n之间的关系为:sn=2^n-1。

 

本文分别讲述两种实现方法:

 

一:位图法:

1)构造一个和集合一样大小的数组A,分别与集合中的某个元素相应,数组A中的元素仅仅有两种状态:“1”和“0”,分别代表每次子集输出中集合中相应元素是否要输出。这样数组A能够看作是原集合的一个标记位图。

2)数组A模拟整数“加一”的操作,每“加一”之后,就将原集合中全部与数组A中值为“1”的相相应的元素输出。

设原集合为<a,b,c,d>。数组A的某次“加一”后的状态为[1,0,1,1],则本次输出的子集为<a,c,d>。

详细代码例如以下:

/*使用非递归的思想 假设有一个数组  大小为n
  那么就使用n 位的二进制 假设对应的位为1 那么就输出这个位 
  假设对应的位为0 那么就不输出这个位*/

/*
   使用位图的思想 构造一个位集合 大小和数组大小一样,假设位图中对应的
   位为1,表示能够输出这个数组中的元素 假设位图中对应位为0 表示数组中对应位不输出
   这里模拟位图使用的数组 ,这里的重点是模拟数组加1的操作
 */

/*使用数组模拟位图加1的操作  数组能够一直加1  直到数组内全部元素都是1

  函数返回值为bool 数组初始化最高位为1*/
#define MAX_LEN 10
void bitmap(char str[],const int n)
{
	bitset<MAX_LEN> count;
	wang.set();
	int i=0;
	unsigned long value = wang.to_ulong();
	cout<<wang<<" "<<value<<endl;
	int count=0;
	while(value)
	{
		bitset<MAX_LEN> bit(value--);

		for(i=0;i<bit.size();i++)
			if(bit[i])
				cout<<str[i];
		cout<<endl;
		count++;
	}
	cout<<count<<endl;
}

3)时间复杂度:O(n*2^n)。事实上,在遍历输出子集的过程中。能够对程序做进一步的优化。

比如。在第m次迭代中。仅仅须要遍历前k个元素,k=log2(m)+1。这样,不考虑数组模拟”加一”操作的话,总遍历次数为Sn=(n-2)*2^n+2,n>=2;Sn=1,n=1。尽管复杂度不变,但总执行时间会降低。

4)空间复杂度:该方法每次迭代都是独立进行,与上次迭代的结果没有不论什么关系。因此每次输出子集之后内存都能够被反复利用。

仅仅须要一个与原集合相同大小的数组。空间复杂度为O(n)。

 

 

二:递归迭代法:

1)採用递归迭代。详细步骤例如以下,

设。原始集合s=<a,b,c,d>,子集结果为r:

第一次迭代:

r=<a>

第二次迭代:

r=<a ab b>

第三次迭代:

r=<a ab b ac abc bc c>

第四次迭代:

r=<a ab b ac abc bc c ad abd bd acd abcd bcd cd d>

 

每次迭代,都是上一次迭代的结果+上次迭代结果中每一个元素都加上当前迭代的元素+当前迭代的元素。

详细代码例如以下:

/*上述方法不可用 明确递归的思想 以下每次都是输出back中的字符就可以 
  这次输出的子集就是上次输出的子集 +这次迭代的元素 + 这次迭代的元素的本身*/
#if 1
void print(char* str)
{
	/*使用两个数组。一个记录上次迭代的结果 
	  一个记录这次须要输出的结果 
	  vec记录的是下次迭代须要參考的子集
	  back记录的是參考vec迭代以后生成新的子集
	 */
	int count=0;
	vector<char> vec;
	vector<char> back;
	int j;
	for(int i=0;i<strlen(str);i++)
	{
		if(i == 0)
		{
			vec.push_back(str[i]);
			vec.push_back(',');
			back=vec;
		}
		else
		{
			for(j=0;j<back.size();j++)
				if(back[j] == ',')
				{
					back.insert(back.begin() +j,str[i]);
					j++;
				}
			back.push_back(str[i]);
			back.push_back(',');			
		}
		for(j=0;j<back.size();j++)
		{
			if(back[j] == ',')
			{
				printf("\r\n");
				count++;
			}
			else
				printf("%c",back[j]);
			if(i)
				vec.push_back(back[j]);

		}
		back=vec;
	}
	printf("sub_set count is %d \r\n",count);
}
#endif

2)时间复杂度

依据上述过程,不难求的。第k次迭代的迭代次数为:2^k-1。

n>=k>=1。迭代n次,总的遍历次数为:2^(n+1)-(2+n),n>=1。

则时间复杂都为O(2^n)。

 

3)空间复杂度

因为该算法。下一次迭代过程都须要上一次迭代的结果,而最后一次迭代之后就没有下一次了。

因此如果原始集合有n个元素。则在迭代过程中,总共须要保存的子集个数为2^(n-1)-1,n>=1。

但须要注意的是,这里之考虑了子集的个数,每一个子集元素的长度都视为1,这点要注意。

总结:

递归是非常耗时的。由于是递归,在第一种方法时,使用了C++中的bitset,这种方法效率非常高,在第二个方法中,使用两个向量的目的是,一个向量记录了这次迭代须要输出的集合,一个向量是为了这次迭代须要參考上次输出的情况。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115429.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • C语言strcat()函数:连接字符串

    C语言strcat()函数:连接字符串

  • 控制结构与一个完整的类

    控制结构与一个完整的类

  • pycharm如何设置背景图片_电话背景图片怎么设置

    pycharm如何设置背景图片_电话背景图片怎么设置打开Pycharm点击左上角File如图:然后选择找到Settings点击进入,打开Appearance&Behavior,选择Appearance如图:最后找到BackgroundImage,选择好自己要设置的图片,Opacity可以调解好透明度,点击OK就可以了看效果:…

  • telnet远程登录AAA认证

    telnet远程登录AAA认证R1<Huawei>system-view//进入全局配置模式[Huawei]sysnameR1//改名[R1]undoinfo-centerenable//关闭信息告警提示[R1]interfaceg0/0/0//进入g/0/0接口[R1-GigabitEthernet0/0/0]ipaddress192.168.100…

  • 三大通信协议(二):IIC通信协议

    三大通信协议(二):IIC通信协议1.概念是什么?I²C(Inter-IntegratedCircuit),中文应该叫集成电路总线,它是一种串行通信总线,使用多主从架构,是由飞利浦公司在1980年代初设计的,方便了主板、嵌入式系统或手机与周边设备组件之间的通讯。由于其简单性,它被广泛用于微控制器与传感器阵列,显示器,IoT设备,EEPROM等之间的通信。优点仅需要两条总线即可通讯(大大的节约了IO口资源)最大主机数量:无限制。最大从机限制:理论127(一个主机多个从机,一对多,多对一,多对多)2.硬件连

  • Java线程池参数分析「建议收藏」

    Java线程池参数分析「建议收藏」线程池组成创建线程池创建线程池通过Executors的工厂方法来创建线程池实例。实际上Executors创建的线程池实例最终都是通过实例化配置不同参数的ThreadPoolExecutor对象。 publicstaticExecutorServicenewFixedThreadPool(intnThreads){returnnewThreadPoolEx…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号