********fp增長算法求出頻繁項集*******/
/********作者：xiaocui************/
/********時間：2006.10.12*********/
/********版本：v1.0**********/

/****fp增長算法：****************
(1)計算各個項的支持度，按降序排列
(2)把各個事務的項按(1)的順序排列
(3)改變各個共根項的計數
(4)以各個單項為尾計算各個頻繁項集
 **************************************/

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using  namespace  std;

vector<vector<char> > VVCHAR;//存放一個集合的所有子集
vector<int> IS_NOT; //記錄各個元素的選與未選
const SUPPORT=3; //支持度
/********返回一個序列中最大元素的索引號******/
int  max_index(const vector<int> & ivec)
{
 int max_num=-100;
 int index;
 for(int i=0;i<ivec.size();++i)
 {
  if(ivec[i]>max_num)
  {
   max_num=ivec[i];
   index=i;
  }
 }
 return  index;
}

//從各個事務的項集中得到數據庫的所有單個項并按支持度排成降序
vector<char>  reverse_unique_item(const vector<vector<char> > & vvchar )
{
 vector<char> cvec;
 vector<int> count;
 vector<char> reverse_cvec;
 for(int i=0;i<vvchar.size();++i)
 {
  for(int j=0;j<vvchar[i].size();++j)
  {
   vector<char>::iterator iter;
   //找不到說明前面沒有重復的單項
   if((iter=find(cvec.begin(),cvec.end(),vvchar[i][j]))==cvec.end())
   {
    cvec.push_back(vvchar[i][j]);
    count.push_back(1);
   }
   else
   {
    count[iter-cvec.begin()]+=1;//在重復元素對應的計數位置加1
   }    
  }
 }
 /******每次從序列中選出支持度最大的項加入倒序序列(不斷刪除最大元素)*****/
    while(count.size()>0)
 {
  int index=max_index(count);
  reverse_cvec.push_back(cvec[index]);
  cvec.erase(cvec.begin()+index);
  count.erase(count.begin()+index);
 }
 return  reverse_cvec;
}

/*******排列各個事務中的項集，參見單項的降序序列*****/
void sort_transaction(const vector<char> &reverse_cvec,
       vector<vector<char> > &vvchar)
{
 for(int i=0;i<vvchar.size();++i)
 {
  vector<int> count;
  for(int j=0;j<vvchar[i].size();++j)
  {   
   vector<char>::const_iterator iter;
   iter=find(reverse_cvec.begin(),reverse_cvec.end(),vvchar[i][j]);
   count.push_back(iter-reverse_cvec.begin());//得到該事務各個項在倒序序列的序號
  }
  vector<char> tmp=vvchar[i];//該事務的副本
  vector<char> reverse_tmp;//該事務的倒序序列
  while(count.size()>0)
  {
   int index=max_index(count);
   reverse_tmp.push_back(tmp[index]);
   tmp.erase(tmp.begin()+index);
   count.erase(count.begin()+index);
  }
  reverse(reverse_tmp.begin(),reverse_tmp.end());
  vvchar[i]=reverse_tmp;//得到倒序序列中的順序
 }
}

/********兩個分支進行比較，檢查2個分支開頭有多少項相同******/
int  root_location(const vector<char> & vchar1, const vector<char> & vchar2)
{
 int i;
 for(i=0;i<vchar1.size();++i)
 {
  if(vchar1[i]!=vchar2[i])
  {
   break;
  }
 }
 return i;
}

/*********改變各個共根項的計數，形成邏輯上的fp樹********/
void count_root(const vector<vector<char> > & vvchar, 
    vector<vector<int> > & vvint)
{
 //初始化，分支上各個單項的計數都為1
 for(int i=0;i<vvchar.size();++i)
 {
  vector<int> ivec;
  for(int j=0;j<vvchar[i].size();++j)
  {
   ivec.push_back(1);
  }
  vvint.push_back(ivec);
 }
 for(int k=0;k<vvchar.size();++k)
 {
  for(int j=k+1;j<vvchar.size();++j)
  {
   int index=root_location(vvchar[k],vvchar[j]);
   if(index!=0)
   {
    for(int i=0;i<index;++i)
    {
     vvint[k][i]+=1;
     vvint[j][i]+=1;
    }
   }
  }
 }
}

/*******對規回溯產生所有一個集合的所有子集************/
void  backtrack(int m, vector<char> cvec)
{
 //本次深度搜索完畢
 if(m>=cvec.size())
 {
  vector<char> vchar;
  for(int i=0;i<cvec.size();++i)
  {
   if(IS_NOT[i]==1)
   {
    vchar.push_back(cvec[i]);
   }
  }
  if(vchar.size()!=0)
  {
   VVCHAR.push_back(vchar);//保留該子集
  }
  return;
 }
 for(int i=0;i<=1;++i)
 {
  //首先記錄本次的選擇
  if(IS_NOT.size()<cvec.size())
  {
   IS_NOT.push_back(i);
  }
  else
  {
   IS_NOT[m]=i;
  }
  backtrack(m+1,cvec);//深度遞歸
 }
}

/********根據邏輯fp樹，以各個單項為尾找出頻繁項集*********/
vector<vector<char> > frequen_collection(const vector<vector<char> > & vvchar,
                                         const vector<vector<int> > & vvint,
           const vector<char> & item,
           int  support)
{
 vector<vector<char> > collection;  
 for(int i=item.size()-1;i>=0;--i)
 {
  //對每個單項，尋找到以它為尾的所有樹枝
  vector<vector<char> > vvchar_tmp;
  for(int j=0;j<vvchar.size();++j)
  {
      if(find(vvchar[j].begin(),vvchar[j].end(),item[i])!=vvchar[j].end())
   {
    vector<char> vchar_tmp;
    for(int k=0;k<find(vvchar[j].begin(),vvchar[j].end(),item[i])-vvchar[j].begin();++k)
    {
     vchar_tmp.push_back(vvchar[j][k]);
    }
    if(vchar_tmp.size()>0)
    {
     vvchar_tmp.push_back(vchar_tmp);
    }
   }
  }
  /********如果該單項前面沒有樹枝，說明是樹頂，單獨考慮*****/
  if(vvchar_tmp.size()==0)
  {
   int item_count=0;
   for(int m=0;m<vvchar.size();++m)
   {
    for(int n=0;n<vvchar[m].size();++n)
    {
     if(vvchar[m][n]==item[i])
     {
      item_count=item_count+1;
     }
    }
   }
   if(item_count>=support)
   {
    vector<char> tmp;
    tmp.push_back(item[i]);
    collection.push_back(tmp);
   }
  }
  /**************找出以該單項為尾的頻繁項集****************/
  if(vvchar_tmp.size()>=support) //如果以該單項為尾的樹枝數大于等于支持度
  {
   /*******計算以該單項為尾的某個樹枝中各項的出現次數******/
   vector<char> vchar_tmp2;
   vector<int> count;
   for(int i1=0;i1<vvchar_tmp.size();++i1)
   {
    for(int j=0;j<vvchar_tmp[i1].size();++j)
    {
     vector<char>::iterator iter;
     if((iter=find(vchar_tmp2.begin(),vchar_tmp2.end(),vvchar_tmp[i1][j]))==vchar_tmp2.end())
     {
      vchar_tmp2.push_back(vvchar_tmp[i1][j]);//第1次添加進去
      count.push_back(1);//第1次添加進去，計數初始化為1
     }
     else
     {
      count[iter-vchar_tmp2.begin()]+=1;
     }
    }
   }
   //首先刪除單項重復次數小于support的項
   for(int k=0;k<count.size();++k)
   {
    if(count[k]<support)
    {
     count.erase(count.begin()+k);
     vchar_tmp2.erase(vchar_tmp2.begin()+k);
     k--;
    }
   }
   //從剩下的單項重復次數均大于支持度的樹枝中生成頻繁項集
   //等價于生成集合的子集
   backtrack(0,vchar_tmp2);//遞歸生成全部子集，保存在VVCHAR
   for(int index=0;index<VVCHAR.size();++index)
   {
    VVCHAR[index].push_back(item[i]);
    collection.push_back(VVCHAR[index]);
   }
      int item_count=0;
   for(int m=0;m<vvchar.size();++m)
   {
    for(int n=0;n<vvchar[m].size();++n)
    {
     if(vvchar[m][n]==item[i])
     {
      item_count=item_count+1;
     }
    }
   }
   if(item_count>=support)
   {
    vector<char> tmp;
    tmp.push_back(item[i]);
    collection.push_back(tmp);
   }
   VVCHAR.erase(VVCHAR.begin(),VVCHAR.end());
   IS_NOT.erase(IS_NOT.begin(),IS_NOT.end());
  }
 }
 return  collection;
}

/**********輸出顯示*********/
void  print(vector<vector<char> > vvchar)
{
 for(int i=0;i<vvchar.size();++i)
 {
  for(int j=0;j<vvchar[i].size();++j)
  {
   cout<<vvchar[i][j];
  }
  cout<<endl;
 }
}

void main()
{
 //從事務文件中把各個事務寫到vvchar中
 ifstream  input=ifstream("transaction.txt");
 vector<vector<char> > transaction;//事務集合
 vector<vector<int> > count;//樹枝上各點的計數
 vector<vector<char> > collection;//頻繁項集
 if (input==0) //文件打開失敗
 {
  cout<<"存放事務的文件transction不存在，請先手工建立"<<endl;
 }
 else
 {
  while(input)
  {
   string  str;
   getline(input,str,'\n'); //得到一行事務項集
   if(str!="")//最后有一空行，所以在此用if消除
   {
    vector<char> cvec;
    for(int i=0;i<str.size();++i)
    {    
     cvec.push_back(str[i]);
    }
    transaction.push_back(cvec);
   }
  }
 }
    vector<char> reverse_cvec=reverse_unique_item(transaction);//得到按支持度降序的項集合
 sort_transaction(reverse_cvec,transaction);//把各個事務的項按降序項集和重排
 count_root(transaction,count);//改變同根計數，形成邏輯fp樹
 collection=frequen_collection(transaction,count,reverse_cvec,SUPPORT);
 //輸出頻繁項集
 cout<<"經過fp增長算法得到的頻繁項集為："<<endl;
 print(collection);
}