集合划分问题（c语言输出集合数目以及不同的集合）

2024-04-07 22:03:09

问题：n个元素的集合{1，2，…，n}可以划分若干非空子集。例如，当n=4时，集合{1，2，3，4}可以划分为15个不同的非空子集如下：
{{1},{2},{3},{4}} {{1,3},{2,4}}
{{1,2},{3},{4}} {{1,4},{2,3}}
{{1,3},{2},{4}} {{1,2,3},{4}}
{{1,4},{2},{3}} {{1,2,4},{3}}
{{2,3},{1},{4}} {{1,3,4},{2}}
{{2,4},{1},{3}} {{2,3,4},{1}}
{{3,4},{1},{2}} {{1,2,3,4}}
{{1,2},{3,4}}
给定正整数n，计算出n个元素的集合{1,2,，…，n}可以划分为多少个不同的非空子集。
输出集合数目及不同的集合。
测试数据为5和6

运行结果附图

————————————————
版权声明：本文为CSDN博主「小西柚code」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_52275819/article/details/120469362

运行结果附图

代码如下：

#include <iostream>
using namespace std;
int a[101][101],b[101]={0};//a里面存储集合元素，b存储集合元素个数 
int n,sum=0,M;//sum记录总数，M存储最原先要划分的集合个数 
int tongji(int c,int m)//b为数字个数，m为所划分集合个数 
{
	int i,j;
	if(m==1||c==m)//当满足条件m等于1或c和m相等时输出 
	{
		cout<<'{';//输出左边最外面的花括号 
		if(m==1)//当m为1时 
		{
			cout<<'{';//输出{
			for(i=1;i<=c;)//把1到c的所有数字当作第一组输出 
			{
				if(i!=1) cout<<',';
				cout<<i++;
			}
			for(i=0;i<b[1];)//合并数组存储的第一组的元素
			{
				cout<<',';
				cout<<a[1][i++];
			}	
			cout<<'}';//输出}
			for(j=2;j<=M;j++)//输出a数组存储的几个集合 
			{
				cout<<',';//输出逗号分隔集合
				cout<<'{';//输出{
				for(i=0;i<b[j];)
				{
					if(i!=0) cout<<',';
					cout<<a[j][i++];
				}
				cout<<'}';//输出}
			}
			
		}
		else//c==m的情况下
		{
			for(j=1;j<=M;j++)//把1-c分别作为1-c组集合的元素 
			{
				if(j!=1)  cout<<',';//输出逗号分隔集合，第一组不用 
				cout<<'{';//输出{
				if(j<=c) cout<<j;//把j作为j组集合的元素输出 
				for(i=0;i<b[j];)//输出a数组存储的几个集合
				{
					if(j<=m||i!=0) cout<<',';
					cout<<a[j][i++];
				}
				cout<<'}';//输出}
			}
		}
		cout<<'}'<<endl;//输出右边最外面的花括号，换行 
		sum++;//总数加一 
	}
	else
	{
		a[m][b[m]++]=c;
		tongji(c-1,m-1);
		b[m]--;//还原为原来的数组 
		for(i=1;i<=m;i++)//让数字c存储在第1到第m个集合，再递归 
		{
			a[i][b[i]++]=c; //让数字c存储在第i个集合
			tongji(c-1,m); //继续递归调用自身 
			b[i]--;//还原为原来的数组
		}
	}
}
int main()
{
	int n,i;
	cin>>n;//输入n 
	for(i=1;i<=n;i++)//按划分数组个数来划分种类 
	{
		cout<<"划分为"<<i<<"个数组的情况有："<<endl; 
		M=i;//用M存储最原先要划分的集合个数 
		tongji(n,i);//套用函数，划分为i个集合
	}
	cout<<"总共有"<<sum<<"种情况"<<endl;//输出总数 
}

谢谢浏览，如果对你有用点个赞呗！

码农公寓

相关文章