登 录
大概一年前写代码实现了这个算法，今天有人问我要，在这里贴出来好了。具体算法思路我也忘了，但是代码应该还算清晰。只需要事先了解下STL。
/* 测试数据<br /> 21/10 X1 X2 X3 X4 X5 X6 X7 X8 X9 y<br /> U1 c 6 y E m h h a m m<br /> U2 c 6 n E m m h ma m m<br /> U3 c 6 n E m h h ma m m<br /> U4 c 4 y E m h h ma l h<br /> U5 c 6 n E m m m ma m m<br /> U6 c 6 n B m m m a he lo<br /> U7 c 6 n E m m h ma he lo<br /> U8 s 4 n B sm h lo ma l h<br /> U9 c 4 n B sm h lo ma m m<br /> U10 c 4 n B sm h m a m m<br /> U11 s 4 n E sm h lo ma l h<br /> U12 s 4 n E m m m ma m h<br /> U13 c 4 n B m m m ma m m<br /> U14 s 4 y E sm h h ma m h<br /> U15 s 4 n B sm m lo ma m h<br /> U16 c 4 y E m m h ma m m<br /> U17 c 6 n E m m h a m m<br /> U18 c 4 n E m m h a m m<br /> U19 s 4 n E sm h m ma m h<br /> U20 c 4 n E sm h m ma m h<br /> U21 c 4 n B sm h m ma m m<br /> */<br /> #include <iostream><br /> #include <fstream><br /> #include <vector><br /> #include <set><br /> #include <string><br /> #include <iomanip><br /> using namespace std;<br /> #define DATA_FILE_NAME "../data.txt"<br /> #define DEF_ATTR_CNT 10<br /> #define DEF_OBJ_CNT 21<br /> int g_attr_cnt = 0;<br /> int g_obj_cnt = 0;<br /> class object;<br /> vector<string> g_attr_set;<br /> vector<bool> g_mask;<br /> vector<object *> g_obj_set;<br /> vector<string> g_core_set;<br /> vector<string> g_b_set;<br /> vector<vector<object *> * > g_ind_c_set;<br /> vector<vector<object *> * > g_ind_b_set;<br /> void clr_mask(const string &attr)<br /> {<br /> int i = 0;<br /> for (i = 0; i < g_attr_cnt; i++)<br /> {<br /> if (attr == g_attr_set[i])<br /> g_mask[i] = false;<br /> else<br /> g_mask[i] = true;<br /> }<br /> }<br /> void set_mask()<br /> {<br /> int i = 0;<br /> for (i = 0; i < g_attr_cnt; i++)<br /> {<br /> g_mask[i] = true;<br /> }<br /> }<br /> void set_mask_set(vector<string> &str_set)<br /> {<br /> int i = 0, j = 0;<br /> bool found = false;<br /> for (i = 0; i < g_attr_cnt; i++)<br /> {<br /> found = false;<br /> for (j = 0; j < str_set.size(); j++)<br /> {<br /> if (g_attr_set[i] == str_set[j])<br /> {<br /> found = true;<br /> break;<br /> }<br /> }<br /> if (found)<br /> g_mask[i] = true;<br /> else<br /> g_mask[i] = false;<br /> }<br /> }<br /> class object {<br /> public:<br /> vector<string> attr_val;<br /> string obj_name;</p> <p>public:<br /> object(const string &name) : obj_name(name)<br /> {<br /> attr_val.reserve(DEF_ATTR_CNT);<br /> }<br /> ~object()<br /> { }<br /> bool operator == (const object &r_obj) const<br /> {<br /> bool res = true;<br /> int i = 0;<br /> for (i = 0; i < g_attr_cnt; i++)<br /> {<br /> if (g_mask[i])<br /> res &= (attr_val[i] == r_obj.attr_val[i]);<br /> if (false == res)<br /> break;<br /> }<br /> return res;<br /> }<br /> };<br /> void read_data()<br /> {<br /> string strTmp;<br /> ifstream data_in(DATA_FILE_NAME,ifstream::in);<br /> int i = 0, j = 0;<br /> object *p_obj = NULL;<br /> g_attr_set.reserve(DEF_ATTR_CNT);<br /> g_mask.reserve(DEF_ATTR_CNT);<br /> g_obj_set.reserve(DEF_OBJ_CNT);<br /> // read object count, and attr count<br /> data_in >> strTmp;<br /> g_obj_cnt = atoi(strTmp.substr(0, strTmp.find("/")).c_str());<br /> g_attr_cnt = atoi(strTmp.substr(strTmp.find("/") + 1, strTmp.length()).c_str());<br /> for (i = 0; i < g_attr_cnt; i++)<br /> {<br /> data_in >> strTmp;<br /> g_attr_set.push_back(strTmp);<br /> g_mask.push_back(true);<br /> }<br /> for (i = 0; i < g_obj_cnt; i++)<br /> {<br /> data_in >> strTmp;<br /> p_obj = new object(strTmp);<br /> for (j = 0; j < g_attr_cnt; j++)<br /> {<br /> data_in >> strTmp;<br /> p_obj->attr_val.push_back(strTmp);<br /> }<br /> // add object<br /> g_obj_set.push_back(p_obj);<br /> }<br /> // close file<br /> data_in.close();<br /> }<br /> void print_data()<br /> {<br /> int i = 0, j = 0;<br /> cout << g_obj_cnt << "/" << g_attr_cnt << " ";<br /> for (i = 0; i < g_attr_cnt; i++)<br /> {<br /> cout << setw(4) << setiosflags(ios::left) << g_attr_set[i];<br /> if (i < g_attr_cnt - 1)<br /> cout << " ";<br /> }<br /> cout << endl;<br /> cout << "-------------------------------------------------------------------------" << endl;</p> <p> for (i = 0; i < g_obj_cnt; i++)<br /> {<br /> cout << setw(3) << g_obj_set[i]->obj_name << " ";<br /> for (j = 0; j < g_attr_cnt; j++)<br /> {<br /> cout << setw(3) << setiosflags(ios::left) << g_obj_set[i]->attr_val[j];<br /> if (j < g_attr_cnt - 1)<br /> cout << setw(3) << " ";<br /> }<br /> cout << endl;<br /> }<br /> }<br /> void clear_data()<br /> {<br /> int i = 0;<br /> for (i = 0; i < g_obj_cnt; i++)<br /> {<br /> delete g_obj_set[i];<br /> g_obj_set[i] = NULL;<br /> }<br /> }<br /> void clear_ind_set(vector<vector<object *> * > &ind_set)<br /> {<br /> vector<object *> *tmp = NULL;<br /> while (!ind_set.empty())<br /> {<br /> tmp = ind_set.back();<br /> delete tmp;<br /> tmp = NULL;<br /> ind_set.pop_back();<br /> }<br /> }<br /> void app_exit()<br /> {<br /> clear_ind_set(g_ind_c_set);<br /> clear_ind_set(g_ind_b_set);<br /> }<br /> void add_obj_to_ind_set(vector<vector<object *> * > &ind_set, object *p_obj)<br /> {<br /> vector<object *> *vec_tmp = NULL;<br /> int i = 0;<br /> bool found = false;<br /> for (i = 0; i < ind_set.size(); i++)<br /> {<br /> if ((*p_obj) == *((*ind_set[i])[0]))<br /> {<br /> found = true;<br /> ind_set[i]->push_back(p_obj);<br /> break;<br /> }<br /> }<br /> if (!found)<br /> {<br /> vec_tmp = new vector<object *>;<br /> vec_tmp->push_back(p_obj);<br /> ind_set.push_back(vec_tmp);<br /> }<br /> }<br /> bool obj_set_equal(vector<object *> &l_obj_set, vector<object *> &r_obj_set)<br /> {<br /> if (l_obj_set.size() != r_obj_set.size())<br /> return false;<br /> bool found = false;<br /> int i = 0, j = 0;<br /> for (i = 0; i < l_obj_set.size(); i++)<br /> {<br /> found = false;<br /> for (j = 0; j < r_obj_set.size(); j++)<br /> {<br /> if (l_obj_set[i] == r_obj_set[j])<br /> {<br /> found = true;<br /> break;<br /> }<br /> }<br /> if (!found)<br /> return false;<br /> }<br /> return true;<br /> }<br /> bool ind_set_equal(vector<vector<object *> * > &l_ind_set, vector<vector<object *> * > &r_ind_set)<br /> {<br /> if (l_ind_set.size() != r_ind_set.size())<br /> return false;<br /> bool found = false;<br /> int i = 0, j = 0;<br /> for (i = 0; i < l_ind_set.size(); i++)<br /> {<br /> found = false;<br /> for (j = 0; j < r_ind_set.size(); j++)<br /> {<br /> if (obj_set_equal(*l_ind_set[i], *r_ind_set[j]))<br /> {<br /> found = true;<br /> break;<br /> }<br /> }<br /> if (!found)<br /> return false;<br /> }<br /> return true;<br /> }<br /> void core()<br /> {<br /> // get IND(C)<br /> int i = 0;<br /> vector<vector<object *> * > ind_set_tmp;<br /> set_mask();<br /> for (i = 0; i < g_obj_cnt; i++)<br /> {<br /> add_obj_to_ind_set(g_ind_c_set, g_obj_set[i]);<br /> }<br /> int j = 0;<br /> for (i = 0; i < g_attr_cnt; i++)<br /> {<br /> clear_ind_set(ind_set_tmp);<br /> clr_mask(g_attr_set[i]);<br /> // get IND(C-{xi})<br /> for (j = 0; j < g_obj_cnt; j++)<br /> {<br /> add_obj_to_ind_set(ind_set_tmp, g_obj_set[j]);<br /> }<br /> if (!ind_set_equal(g_ind_c_set, ind_set_tmp))<br /> g_core_set.push_back(g_attr_set[i]);<br /> }<br /> clear_ind_set(ind_set_tmp);<br /> // already get core<br /> cout << "-------------------------------------------------------------------------" << endl;<br /> cout << "core:/n{";<br /> for (i = 0; i < g_core_set.size(); i++)<br /> {<br /> //copy to B<br /> g_b_set.push_back(g_core_set[i]);<br /> cout << g_core_set[i];<br /> if (i < g_core_set.size() - 1)<br /> cout << ", ";<br /> }<br /> cout << "}/n";<br /> }<br /> bool attr_set_equal(vector<string> &l_attr_set, vector<string> &r_attr_set)<br /> {<br /> if (l_attr_set.size() != r_attr_set.size())<br /> return false;<br /> int i = 0, j = 0;<br /> bool found = false;<br /> for (i = 0; i < l_attr_set.size(); i++)<br /> {<br /> found = false;<br /> for (j = 0; j < r_attr_set.size(); j++)<br /> {<br /> if (l_attr_set[i] == r_attr_set[j])<br /> {<br /> found = true;<br /> break;<br /> }<br /> }<br /> if (!found)<br /> return false;<br /> }<br /> return true;<br /> }<br /> void attr_set_sub(vector<string> &l_attr_set, vector<string> &r_attr_set, vector<string> &res_set)<br /> {<br /> int i = 0, j = 0;<br /> bool found = false;<br /> for (i = 0; i < l_attr_set.size(); i++)<br /> {<br /> found = false;<br /> for (j = 0; j < r_attr_set.size(); j++)<br /> {<br /> if (l_attr_set[i] == r_attr_set[j])<br /> {<br /> found = true;<br /> break;<br /> }<br /> }<br /> if (!found)<br /> res_set.push_back(l_attr_set[i]);<br /> }<br /> }<br /> void get_ind_set(vector<string> &mask_set, vector<vector<object *> * > &res_ind_set)<br /> {<br /> int i = 0;<br /> // get IND set<br /> set_mask_set(mask_set);<br /> for (i = 0; i < g_obj_cnt; i++)<br /> {<br /> add_obj_to_ind_set(res_ind_set, g_obj_set[i]);<br /> }<br /> }<br /> void attr_set_copy(vector<string> &dst_attr_set, vector<string> &src_attr_set)<br /> {<br /> int i = 0;<br /> dst_attr_set.clear();<br /> for (i = 0; i < src_attr_set.size(); i++)<br /> {<br /> dst_attr_set.push_back(src_attr_set[i]);<br /> }<br /> }<br /> void reduction()<br /> {<br /> vector<string> b_set_tmp;<br /> vector<string> c_sub_b;<br /> vector<int> max_sig;<br /> vector<vector<object *> * > ind_set_tmp;<br /> int max = 0, max_idx = 0, max_cnt = 0;<br /> int i = 0, j = 0;<br /> // get IND(B)<br /> get_ind_set(g_b_set, g_ind_b_set);<br /> while (!ind_set_equal(g_ind_c_set, g_ind_b_set))<br /> {<br /> if (attr_set_equal(g_b_set, g_attr_set))<br /> break;<br /> c_sub_b.clear();<br /> attr_set_sub(g_attr_set, g_b_set, c_sub_b);<br /> max_sig.clear();<br /> for (i = 0; i < c_sub_b.size(); i++)<br /> {<br /> attr_set_copy(b_set_tmp, g_b_set);<br /> b_set_tmp.push_back(c_sub_b[i]);<br /> clear_ind_set(ind_set_tmp);<br /> get_ind_set(b_set_tmp, ind_set_tmp);<br /> max_sig.push_back(ind_set_tmp.size() - g_ind_b_set.size());<br /> }<br /> // now, process max_sig<br /> max = max_sig[0];<br /> max_idx = 0;<br /> max_cnt = 0;</p> <p> for (j = 1; j < max_sig.size(); j++)<br /> {<br /> if (max_sig[j] > max)<br /> {<br /> max = max_sig[j];<br /> max_idx = j;<br /> max_cnt = 1;<br /> }<br /> else if (max == max_sig[j])<br /> {<br /> max_cnt++;<br /> }<br /> }<br /> g_b_set.push_back(c_sub_b[max_idx]);<br /> if (attr_set_equal(g_b_set, g_attr_set))<br /> break;<br /> // get IND(B)<br /> clear_ind_set(g_ind_b_set);<br /> get_ind_set(g_b_set, g_ind_b_set);<br /> }<br /> clear_ind_set(ind_set_tmp);<br /> // get reduction now<br /> cout << "-------------------------------------------------------------------------" << endl;<br /> cout << "reduction set:/n{";<br /> for (i = 0; i < g_b_set.size(); i++)<br /> {<br /> cout << g_b_set[i];<br /> if (i < g_b_set.size() - 1)<br /> cout << ", ";<br /> }<br /> cout << "}/n";<br /> }<br /> void print_red_data()<br /> {<br /> int i = 0, j = 0;<br /> set_mask_set(g_b_set);<br /> cout << "-------------------------------------------------------------------------" << endl;<br /> cout << " ";<br /> for (i = 0; i < g_attr_cnt; i++)<br /> {<br /> if (g_mask[i])<br /> {<br /> cout << setw(4) << setiosflags(ios::left) << g_attr_set[i];<br /> if (i < g_attr_cnt - 1)<br /> cout << " ";<br /> }<br /> }<br /> cout << endl;<br /> cout << "-------------------------------------------------------------------------" << endl;</p> <p> for (i = 0; i < g_obj_cnt; i++)<br /> {<br /> cout << setw(3) << g_obj_set[i]->obj_name << " ";<br /> for (j = 0; j < g_attr_cnt; j++)<br /> {<br /> if (g_mask[j])<br /> {<br /> cout << setw(3) << setiosflags(ios::left) << g_obj_set[i]->attr_val[j];<br /> if (j < g_attr_cnt - 1)<br /> cout << setw(3) << " ";<br /> }<br /> }<br /> cout << endl;<br /> }<br /> }<br /> int main()<br /> {<br /> read_data();<br /> print_data();<br /> core();<br /> reduction();<br /> print_red_data();<br /> clear_data();<br /> app_exit();<br /> }<br />
抱歉!评论已关闭.