集合的算法！

Question

有n个集合，每个集合包含若干个不同的整数，数目都小于或等于m，现在要将这n个集合分组，每个分组要求包含的不同的整数个数仍小于或等于m，问如何使分组个数最少？

Answer 1

把n个集合的元素个数加起来，再初以m
Y=(X1+X2+X3+...+Xn)/m

Answer 2

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define LEN 4
char* dat(char* str,int a);
int ind(char* str);
int deg(int x);
int dim(int* data,int m,int n);
char dat01[4];
int sum;
void main()
{
int m=3;
int n=3;
char str[40]="{1,2},{2,3},{1,3,4}";
// cout<<"请输入两个自然数n和m,要求n>m:\n";
// cin>>n>>m;
int* data=new int[n];
// cout<<"请输入"<<n<<"个形如: {1,2},{2,3},{1,3,4}的"<<m<<"_子集序列,要求每个元素为<4的自然数\n";
// cin>>str;
for(int i=0;i<n;i++)
data[i]=ind(dat(str,i));
cout<<dim(data,m,n)<<endl;
delete data;
}char* dat(char* str,int a)//第a+1号子集的二进制表示
{
for(int i=0;i<LEN;i++) dat01[i]='0';
i=0;int j=-1;
while(str[i]!='\0')
{
if(str[i]=='{') j++;
if(j==a) break;
i++;
}
while(str[i]!='}' && str[i]!='\0')
{
if(str[i]=='{' || str[i]==',')
dat01[LEN-atoi(str+i+1)]='1';
i++;
}
return dat01;
}
int ind(char* str)//二进制化为十进制
{
sum=0;
for(int i=0;i<LEN;i++)
if(str[i]=='1') sum+=(long)pow(2,LEN-1-i);
return sum;
}
int deg(int x)//x变为二进制时1的个数
{
char st[LEN+1]="";
itoa(x,st,2);
int sum=0;
int t=strlen(st);
for(int i=0;i<t;i++)
if(st[i]=='1') sum++;
return sum;
}
int dim(int* data,int m,int n)//集合族对应数组的递归算法
{
int a=n,b=n;
if(n==1) return 1;
for(int i=0;i<n-1;i++)
{
if(deg(data[i] | data[n-1])<=m) 
{
int* tem=data;
tem[i]|=tem[n-1];
a=dim(tem,m,n-1);
if(a<b) b=a;
}
}
if(b==n) return 1+dim(data,m,n-1);
return b;
}

Answer 3

将char dat01[4];改为char dat01[LEN+1];
改变#define LEN 4，去掉//时可实现一般化。

Answer 4

改进后的算法：
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stdio.h>
int trim(char* str);
int dat(char* str,int p,int a);
int deg(int x);
int dim(int* data,int m,int n,int p);
int len;void main()
{//去掉下面的//对一般集合成立
int m=4,n=0,i=0;
// cout<<"请输入子集的长度上限m：\n";
// cin>>m;
char str[1000]="{1,ab,5},{1,ab,3,6},{1,3,4},{1,ab,5,6},{ab,3,5},{6,ab,5}";
// cout<<"请输入形如: {1,2},{ad,3},{1,3,4}的集合序列,要求每个集和的元素个数 <= "<<m<<" \n";
// cin>>str;
while(str[i]!=0)
{
if(str[i]=='{') n++;
i++;
}
int* data=new int[n];
int p=trim(str);
if(p==0) cout<<"输入有误"<<endl;
cout<<"标准化后的集合族：\n"<<str<<endl;
cout<<"集合族关于 "<<p<<" 的十进制表示: \n";
for(i=0;i<n;i++)
{
data[i]=dat(str,p,i);
cout<<data[i]<<"   ";
}
cout<<endl<<"集合族关于 "<<m<<" 的最小重组数 "<<dim(data,m,n,p)<<endl;
delete data;
}int trim(char* str)//集合标准化
{
int len=strlen(str);
if(str[0]!='{' || str[len-1]!='}') return 0;
for(int i=len-1;i>=0;i--)
if(str[i]==',' || str[i]=='{') break;
if(i==len-2) return 0;
if(i==0) {strcpy(str,"{1}");return 1;}
int dx=len-i-2,k=0;
for(int j=0;j<i;j++)
{
if(strncmp(str+j,str+i+1,dx)==0 
&& (str[j-1]=='{' || str[j-1]==',')
    && (str[j+dx]=='}' || str[j+dx]==','))
break;
if(str[j]==',') k++;
} int a=i,b=0;
if(str[i]==',') {b=1;str[i]='}';}//逗点情况
if(str[i]=='{') 
{
b=0;
if(str[i-1]==',' && str[i-2]=='}') i-=2; 
else return 0;
}
str[i+1]='\0';
int max=trim(str); if(max==0) return 0; char tem[20]="";len=strlen(str);
if(j==a) 
{
max++;
sprintf(tem,"%d",max);
}
else
{
int s=0;
for(int t=0;t<len;t++)
{
if(str[t]==',') s++;if(s==k) break;
}
t++;if(str[t]=='{') t++;
int min=atoi(str+t);
sprintf(tem,"%d",min);
}

if(b==1)//逗点情况
str[len-1]=',';
else
strcat(str,",{");
strcat(str,tem);
strcat(str,"}");
return max;
}int dat(char* str,int p,int a)//第a+1个子集关于p的十进制表示
{
char* d01=new char[p+1];
for(int i=0;i<p;i++) d01[i]='0';
i=0;int j=-1;
while(str[i]!='\0')
{
if(str[i]=='{') j++;
if(j==a) break;
i++;
}
while(str[i]!='}' && str[i]!='\0')
{
if(str[i]=='{' || str[i]==',')
d01[p-atoi(str+i+1)]='1';
i++;
}
int sum=0;
for(i=0;i<p;i++)
if(d01[i]=='1') sum+=(int)pow(2,p-1-i);
delete d01;
return sum;
}int deg(int x,int p)//x的二进制取1个数
{
char* st=new char[p+1];
itoa(x,st,2);
int sum=0;
int t=strlen(st);
for(int i=0;i<t;i++)
if(st[i]=='1') sum++;
delete st;
return sum;
}
int dim(int* data,int m,int n,int p)//集合族对应数组的递归算法
{
int a=n,b=n;
if(n==1) return 1;
if(deg(data[n-1],p)>m) 
cout<<"输入有误"<<endl;
for(int i=0;i<n-1;i++)
{
if(deg(data[i],p)>m) cout<<"输入有误"<<endl;
if(deg(data[i] | data[n-1],p)<=m) //集合的并运算
{
int* tem=data;
tem[i]|=tem[n-1];
a=dim(tem,m,n-1,p);
if(a<b) b=a;
}
}
if(b==n) return 1+dim(data,m,n-1,p);
return b;
}

Answer 5

也许写一大段的程序，你也难得看，我就说说我的想法吧，其实这个问题很简单，全部都是整数，这样是很好处理的。bool a[5000]={false}  //最大的整数为5000。{
   for (i=0;i<n;i++)
     .... //计算元素，如果k是元素，则使a[k]=ture.
   j=0;
   for (i=0;i<=5000;i++) if (a[i]) j++; //统计元素个数
   
   k=j/m+(j%m!=0); //得出可以分出多少组
   for (i=0;i<=5000;i++) 
     .... //每次取是a[i]为ture的数进行分组，且每组m个数，注意最后一组数。}

Answer 6

楼上好象误解了楼主的本意。我也举例说说我的算法。
    集合组“{ab,2},{2,3},{ab,3,8}”由集合{ab，2，3，8}的子集构成，为了实现集合的并运算，采用二进制算法，分别用1000，0100，0010，0001表示ab，2，3，8，则集合{ab，2}可用1000+0100=1100表示，集合{2，3}可用0100+0010=0110表示，集合{ab，3，8}可用1000+0010+0001=1011表示。集合{ab，2}∪{2，3}可用或运算表示，即1100 | 0110=1110。这样集合组“{ab,2},{2,3},{ab,3,8}”在并运算下的限长重组问题就转化成数字1100，0110，1011之间在或运算下的限长重组问题，可用递归简单实现。
    注意，集合组“{ab,2},{2,3},{ab,3,8}”在并运算下的限长重组≠构成集{ab，2，3，8}的限长分组。