//FP增長(zhǎng)樹2007-07-12?19:41/******fp增長(zhǎng)算法求出頻繁項(xiàng)集

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

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

vector?>?VVCHAR;//存放一個(gè)集合的所有子集
vector?IS_NOT;?//記錄各個(gè)元素的選與未選
//const?static?SUPPORT=2;?//支持度
/********返回一個(gè)序列中最大元素的索引號(hào)******/
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;
}

//從各個(gè)事務(wù)的項(xiàng)集中得到數(shù)據(jù)庫(kù)的所有單個(gè)項(xiàng)并按支持度排成降序
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;
????//找不到說(shuō)明前面沒(méi)有重復(fù)的單項(xiàng)
????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ù)元素對(duì)應(yīng)的計(jì)數(shù)位置加1
????}
???}
}
/******每次從序列中選出支持度最大的項(xiàng)加入倒序序列（不斷刪除最大元素）*****/
?????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;
}

/*******排列各個(gè)事務(wù)中的項(xiàng)集，參見(jiàn)單項(xiàng)的降序序列*****/
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ù)各個(gè)項(xiàng)在倒序序列的序號(hào)
???}
???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;//得到倒序序列中的順序
}
}

/********兩個(gè)分支進(jìn)行比較，檢查2個(gè)分支開(kāi)頭有多少項(xiàng)相同******/
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;
}

/*********改變各個(gè)共根項(xiàng)的計(jì)數(shù)，形成邏輯上的fp樹********/
void?count_root（const?vector?>?&?vvchar
?????vector?>?&?vvint）
{
//初始化，分支上各個(gè)單項(xiàng)的計(jì)數(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（