//FP增長樹2007-07-12?19:41/******fp增長算法求出頻繁項集

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

#include?
#include?
#include?
#include?
#include?
using???namespace???std;

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

//從各個事務(wù)的項集中得到數(shù)據(jù)庫的所有單個項并按支持度排成降序
vector???reverse_unique_item（const?vector?>?&?vvchar?）
{
vector?cvec;
vector?count;
vector?reverse_cvec;
for（int?i=0;i{
???for（int?j=0;j???{
????vector::iterator?iter;
????//找不到說明前面沒有重復(fù)的單項
????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;//在重復(fù)元素對應(yīng)的計數(shù)位置加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;
}

/*******排列各個事務(wù)中的項集，參見單項的降序序列*****/
void?sort_transaction（const?vector?&reverse_cvec
????????vector?>?&vvchar）
{
for（int?i=0;i{
???vector?count;
???for（int?j=0;j???{
????vector::const_iterator?iter;
????iter=find（reverse_cvec.begin（）reverse_cvec.end（）vvchar[i][j]）;
????count.push_back（iter-reverse_cvec.begin（））;//得到該事務(wù)各個項在倒序序列的序號
???}
???vector?tmp=vvchar[i];//該事務(wù)的副本
???vector?reverse_tmp;//該事務(wù)的倒序序列
???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?&?vchar1?const?vector?&?vchar2）
{
int?i;
for（i=0;i{
//	cout<<“++++++++++++++++++++“;
//	cout<//	cout<???if（vchar1[i]!=vchar2[i]）
???{
????break;
???}
}
return?i;
}

/*********改變各個共根項的計數(shù)，形成邏輯上的fp樹********/
void?count_root（const?vector?>?&?vvchar
?????vector?>?&?vvint）
{
//初始化，分支上各個單項的計數(shù)都為1
for（int?i=0;i{
???vector?ivec;
???for（int?j=0;j???{
	???//cout<????ivec.push_back（1）;
???}
???vvint.push_back（ivec）;
}

for（int?k=0;k{
???for（int?j=k+1;j???{

????int?index=root_location（vvchar[k]vvchar[j]）;
????if（index!=0）
????{
?????for（