#include<stdio.h>
typedef  struct 
{
int item[10];  //數據項
} D_Node;      //數據庫D


typedef  struct 
{
int item[10];  //數據項,用item[0]保存支持度

} C_Node; //候選集

typedef  struct 
{
int item[10];  //數據項,用item[0]保存支持度
} L_Node;//頻繁集

C_Node C[20][10];
L_Node L[20][10];
D_Node D[20];

int min_supp;  //最小支持度



void  InPut()
{
 int i,j,n,n1;
 printf("請輸入最小支持度:");
 scanf("%d",&min_supp);
  printf("請輸入交易集的大小");
  scanf("%d",&D[0].item[0]);
  n=D[0].item[0];

     for(i=1;i<=n;i++)  //for1
     {   
        printf("請輸入交易[%d]中記錄的個數(n)",i);
         scanf("%d",&n1);
         D[i].item[0]=n1;

           for(j=1;j<=n1;j++)  //for2
           {
              printf("請輸入交易[%d]中記錄項，直接輸入數字:",i);
             scanf("%d",&D[i].item[j]);              				
           }//for2
             	   
           }  //for1
     
     }//end of InPut


void  C1()
{
	//功能：掃描數據集D生成1項候選集C1
	//輸入：數據集D
	//輸出1項候選集C1
	//初始條件 數據集D 非空
   int i,j,k;
   int no=1,temp=0;
   C[1][0].item[0]=0;  //1 項集的個數，在本算法中，用C[n][k].item[0]來保存候選集Cn的第k項的支持度
   if(D[0].item[0]!=0)
   {  
      C[1][1].item[1]=D[1].item[1];
          
   }
      
    for(i=1;i<=D[0].item[0];i++)  //for1  
    { 
		
         for(j=1;j<=D[i].item[0];j++)  //for2   
    	 {
               temp=1;
               for(k=1;k<=no;k++)  //for3
			   { 
                  if(C[1][k].item[1]==D[i].item[j])
        		  {
                     C[1][k].item[0]++;  //支持度加1
	                     temp=0;  //
                     				  
                  }   //if

               }//end for3
        	   
          
              if(temp)//生成新的項集
        	  { 
                    C[1][++no].item[1]=D[i].item[j];
                    C[1][no].item[0]=1;				 
        	  } 
       
         }//end for2
   
    } // end  for1

    C[1][0].item[0]=no;//數據項的個數	

}  //end of  C1()


void Cn( int n)
{  
	//用頻繁集Ln-1為基礎，通過連接得到n項候選集Cn
	
 int i,j,k,p,q,s,t,num;
 int no=0,temp=0,count;

 C[n][0].item[0]=0;  //初始化

//printf("in Cn(%d) n=%d\n",n,n);
//printf("in Cn(%d) C[%d][0].item[0]=%d\n",n,n,C[n][0].item[0]);

num=L[n-1][0].item[0];  //num是Ln-1項集的數據個數

   for(i=1;i<=num;i++)  
		
      for(j=i+1;j<=num;j++)   //for2
         {
   
		    temp=1;  //測試是否滿足聯結條件
              if(n>2)//if 1
              {
                  for(k=1;k<n-1;k++)    	//for3	  
              	  {
					 if(L[n-1][i].item[k]!=L[n-1][j].item[k])
                   {  temp=0;
                     break; }//if 1

                    }//end for3

                 }//end if1

                      if(temp==1)//滿足聯結條件
                     {
                          // printf("in if 2  no=%d\n",no);
                     no++;

                    for(p=1;p<=n-1;p++)  
                    C[n][no].item[p]=L[n-1][i].item[p];
                    C[n][no].item[p]=L[n-1][j].item[p-1];
                    C[n][no].item[0]=0;
                         for(q=1;q<=D[0].item[0];q++)  //for5  測試其支持度

						 {    
							 
							 count=0; //count用來記數,當所測試的項存在時,count加1,當count=n時，則子集存在

                               for(s=1;C[n][no].item[s]!=0;s++)  //for6
                	     	   {
                                      for(t=1;t<=D[q].item[0];t++)  //for7
									  {
                                             if(C[n][no].item[s]==D[q].item[t])

											 {   count+=1;
									             break;
											 } 
									  }//end for7
                                     
							   }//end for 6
                           if(count==n) C[n][no].item[0]+=1;//子集存在,第no項的支持度加1
            		     
						 }//end for5
                           
                           
                      C[n][0].item[0]+=1;
					  }//end if2
           }//end for2

     /* num=C[n][0].item[0];
     printf("in Cn(%d) num=%d\n",n,num);
	  for(i=1;i<=num;i++)
		  for(j=0;j<=n;j++)
		  {
			  printf("in Cn(%d) C[%d][%d].item[%d]=%d\n",n,n,i,j,C[n][i].item[j]);
		  } 
	  printf("in Cn(%d) C[%d][0].item[0]=%d\n",n,n,C[n][0].item[0]);  */
	  
}//end of Cn()

void L1()
{   
    int i,j,k;
	j=0;
   L[1][0].item[0]=0;
   
   //printf("C[1][0].item[0]=%d\n",C[1][0].item[0]);

   for(i=1;i<=C[1][0].item[0];i++)
   {    
       if(C[1][i].item[0]>=min_supp)
       {
       j+=1;
        for(k=1;k<=1;k++)
         L[1][j].item[k]=C[1][i].item[k];
        L[1][j].item[0]=C[1][i].item[0];
	//	printf("L[1][%d].item[1]=%d   ",j,L[1][j].item[1]);  測試功能時加的
	//	printf("  -------------%d\n",L[1][j].item[0]);
		
       }
   }//end for1
   L[1][0].item[0]=j;
}//end of L1()

void Ln(int n)
{   
    int i,j,k;
	Cn(n);
    j=0;
    L[n][0].item[0]=0;

	  // printf("in Ln(%d) C[%d][0].item[0]=%d\n",n,n,C[n][0].item[0]);

   for(i=1;i<=C[n][0].item[0];i++)  //for 1
   {
       if(C[n][i].item[0]>=min_supp)
       {
         j+=1;
        for(k=1;k<=n;k++)
         L[n][j].item[k]=C[n][i].item[k];
        L[n][j].item[0]=C[n][i].item[0];	
       }  //end if


   }//end for1

   /*  for(i=1;i<=j;i++)
       for(k=0;k<=n;k++)
	 {printf("L[%d][%d].item[%d]=%d \n",n,i,k,L[n][i].item[k]);
		
	 }   */

L[n][0].item[0]=j; //保存數據的個數

}//end of Ln(int n)


  void  OutPut(int n)
  {
     int i,j,k;
     printf("頻繁項目集L%d如下:\n",n);
     k=L[n][0].item[0];
         if(k!=0)
         { 
             for(i=1;i<=k;i++)
        	 {
                printf("{");
               for(j=1;j<=n;j++)			   
			     printf("  I%d ",L[n][i].item[j]);
			     printf("}        支持度:%d\n",L[n][i].item[0]);
			   		   
    		
             }//for
            
          }
         else                printf("項目集為空\n");
        		 
    	 
  }


  void main()
  {
	int i,n;
	int k;
	for (k=1;k<1000;k++)
	{ n=1;
    InPut();
	C1();//初始化,生成1項候選集C1
	L1();//得到1項頻繁集L1
    while(L[n][0].item[0]!=0)
	{
		n+=1;
        Ln(n);
	}
	for(i=1;i<=n;i++)
        OutPut(i);
	
	}       
  }