#include<iostream>
using namespace std;
struct apriori
{
int a[20];
int length;
int frequent;
};
struct set
{
apriori ap[10];
int length;
};
void init(set &s)
{
//建立一个初始化表,所有数据放在其中
int i,j;
int e;
int count;
cout<<"输入集合的个数"<<endl;
cin>>s.length;
for(i=0;i<s.length;i++)
{
count=0;
s.ap[i].length=0;
cout<<"输入元素的值,以-1结束"<<endl;
cin>>e;
while(e!=-1)
{
while(count!=0&&e<s.ap[i].a[count-1])
{//cout<<"2"<<endl;
s.ap[i].a[count]=s.ap[i].a[count-1];
count--;
}
s.ap[i].a[count]=e;
s.ap[i].length++;
count=s.ap[i].length;
cin>>e;
}
//cout<<s.ap[i].length<<endl;
}
}
void order(set &s)
{
}
void firstfind(set &s0,set &s1)
{
//第一次遍历表,得到所有元素及他们出现的频率
int i,j,k;
s1.length=0;
for(i=0;i<s0.length;i++)
{
for(j=0;j<s0.ap[i].length;j++)
{
for(k=0;k<s1.length;k++)
{ // cout<<s0.ap[i].a[j];
if(s0.ap[i].a[j]==s1.ap[k].a[0])
{
s1.ap[k].frequent++;
break;
}
}
if(k>=s1.length)
{
s1.ap[k].a[0]=s0.ap[i].a[j];
s1.ap[k].length=1;
s1.length++;
s1.ap[k].frequent=1;
}
// cout<<s1.ap[i].length<<s1.ap[i].frequent <<endl<<endl;
}
}
}
void nextfind(apriori* head,apriori* &temp)
{
//k-1次遍历,得到每个子集合出现的频率
}
void join(set& s0,set& s1)
{
//从L(k-1)得到C(k)
}
void in_frequent()
{
//第k次中的每一个集合的子集合是否能在L(K-1)中找到,不能则删去该集合
}
void apriori_gen(set& s0,set& s1)
{
//算法,用来得到C(k)
int i,j,k,m;
set sx,sy;
sx=sy=s0;
s1.length=0;
cout<<"s0.length is : "<<s0.length<<endl;
cout<<"&&&"<<s0.length<<s0.ap[0].a[0]<<s0.ap[0].a[1]<<s0.ap[1].a[0]<<endl;
if(sx.ap[0].length==1)
{
for(i=0;i<sx.length-1;i++)
{
for(j=i+1;j<sx.length;j++)
{
s1.ap[s1.length].a[0]=sx.ap[i].a[0];//for(k=0;k<s1.length*(s1.length-1)/2;k++)
s1.ap[s1.length].a[1]=sx.ap[j].a[0];
s1.ap[s1.length].length=2;
//cout<<" "<<sx.ap[i].a[0]<<" "<<sx.ap[j].a[0]<<endl;
s1.length++;
}
} //cout<<"***"<<s1.length<<s1.ap[0].a[0]<<s1.ap[0].a[1]<<s1.ap[1].a[0]<<endl;
}
else
{
for(i=0;i<sx.length-1;i++)//
{
for(k=i+1;k<sx.length;k++)
{
for(j=0;j<sx.ap[i].length-1;j++)
{cout<<sx.ap[i].a[j]<<sy.ap[k].a[j]<<"*"<<endl;
if(sx.ap[i].a[j]==sy.ap[k].a[j])
continue;else break;}
if((j==sx.ap[i].length-1)&&sx.ap[i].a[j]<sy.ap[k].a[j])
{// cout<<"**";cout<<i<<j<<k<<sx.ap[i].a[j]<<endl;
s1.ap[s1.length].length=0;
for(m=0;m<sx.ap[i].length;m++)
{
s1.ap[s1.length].a[m]=sx.ap[i].a[m];
s1.ap[s1.length].length++;
}
s1.ap[s1.length].a[m]=sy.ap[k].a[j];
s1.ap[s1.length].length++;
s1.length++;
}
}
}
}cout<<"***"<<s1.length<<s1.ap[0].a[0]<<s1.ap[0].a[1]<<s1.ap[0].a[2]<<endl;
}
//_____________________________
bool issubset(apriori p ,apriori q)//p.length??
{ cout<<p.a[0]<<p.a[1]<<endl;
cout<<q.a[0]<<q.a[1]<<endl;
int length=q.length;
int i,k;
for(i=0,k=0;k<p.length&&i<length;i++)
{cout<<p.a[k]<<" "<<q.a[i]<<endl;
if(p.a[k]==q.a[i])
k++;
}
if(k==p.length)
return true;
else
return false;
}
void apriori_total(set& s,set& s0)//s0在s出现的次数
{
//算法,用来统计频率
int length=s0.ap[0].length;
int i,j;
for(i=0;i<s0.length;i++)
{
s0.ap[i].frequent=0;
for(j=0;j<s.length;j++)
if(issubset(s0.ap[i],s.ap[j]))
s0.ap[i].frequent++;
cout<<"s0.ap[i].frequent"<<s0.ap[i].frequent<<i<<endl;
}
}
//________________________________
//________________________________
void delcol(set& s0,int col)
{
//cout<<"将会删除第"<<col <<"列"<<endl;
s0.length--;
if(col==s0.length) return ;
int length=s0.ap[col+1].length;
s0.ap[col].length=length;
s0.ap[col].frequent=s0.ap[col+1].frequent;
s0.ap[col+1].length=0;
int i;
for(i=0;i<length;i++)
s0.ap[col].a[i]=s0.ap[col+1].a[i];
cout<<s0.ap[col].frequent<<endl;
}
void del(set& s0, int sup)
{
//删除不满足条件的集合
int i,j;
int length=s0.length; //cout<<"s0.ap[j].frequent"<<s0.ap[2].frequent<<endl;
for(i=0,j=0;i<length;i++,j++)
{cout<<"**"<<j<<s0.ap[j].frequent<<endl;
if(s0.ap[j].frequent<sup)
{
delcol(s0,j);
j--;cout<<"j"<<j<<endl;
}
}
cout<<"after del, the length is : "<<s0.length<<endl;
}
//_________________________________
//_________________________________
void mintotal(set& s0, int& sup)
{
int frequent=10000;
int length=s0.length;
int i;
for(i=0;i<length;i++)
{
if(s0.ap[i].frequent<frequent)
frequent=s0.ap[i].frequent;
}
sup=frequent;
cout<<"sup is : "<<sup<<endl;
//cin>>sup;
}
//_________________________________
int main()
{
/* int i,j;
int k;
apriori* head = NULL;
apriori* temp = NULL;
apriori* ck = NULL;
apriori* p = NULL;
init(head);
firstfind(head,temp);
for(k = 2 ; temp != NULL; k++)//k 为集合的个数
{ p=temp;
apriori_gen(temp,ck);//用来得到C(k)
apriori_total(head,ck);//用得到的C(k)和原数据比较,得到出现的频率
del(ck);
//在一定时候跳出循环 。什么时候???
temp=ck;
}
*/
int k;
int sup;
set s,result,ck,temp;
init(s);
order(s);
firstfind(s,result);
mintotal(result,sup);
for(k=2;result.length!=0;k++)
{
temp=result;
apriori_gen(result,ck);
apriori_total(s,ck);
del(ck,sup);
result=ck;
}
cout<<"结果是: ";
cout<<temp.length<<endl;
for(int i =0 ;i<temp.length;i++)
{
for(int j=0;j<temp.ap[i].length;j++)
cout<<temp.ap[i].a[j]<<" ";
cout<<endl;
}
return 0;
}