fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <set>
  4. #include<algorithm>
  5. #include <iterator>
  6. using namespace std;
  7.  
  8. int main() {
  9. 	// your code goes here
  10.  
  11. 	/*string data[5][5] = {   {"A","B","FG","C","D"} ,
  12. 							{"B","G","D"},
  13. 							{"B","F","G","AB"},
  14. 							{"F","AB","C","D"},
  15. 							{"A","BC","G","F","DE"}
  16. 	};
  17. 	int min_support = 2;
  18. 	set<char> unique_events; // sets hold unique values
  19. 	map<char, int> unique_support; // map each unique value to it's support
  20.  
  21. 	for (int row = 0; row < 5; row++) {
  22. 		for (int col = 0; col < 5; col++) {
  23. 			for (int s = 0; s < data[row][col].length(); s++) {
  24. 				// looping over the dataset to insert unique events into the set
  25. 				unique_events.insert(data[row][col][s]);
  26. 			}
  27. 		}
  28. 	}
  29.  
  30. 	set<char> ::iterator it;
  31. 	map<char, int> ::iterator t;
  32. 	map<char, int> ::iterator loop;
  33.  
  34. 	// iterating over each event in the set comparing it to the row in the dataset 
  35. 	// (whether it appeared n the row or not) if yes, break from that row incrementing it's support 
  36. 	// in the map
  37. 	for (it = unique_events.begin(); it != unique_events.end(); it++) {
  38. 		for (int row = 0; row < 5; row++) {
  39.  
  40. 			bool found = false;
  41.  
  42. 			for (int col = 0; col < 5; col++) {
  43. 				for (int s = 0; s < data[row][col].length(); s++) {
  44.  
  45. 					if (*it == data[row][col][s]) {
  46. 						//searching for the event in the map exists or not
  47. 						t = unique_support.find(data[row][col][s]);
  48. 						if (t != unique_support.end())
  49. 							t->second++;
  50. 						else					
  51. 							unique_support.insert(pair<char,int>(data[row][col][s],1));
  52. 						found = true;
  53. 					}
  54. 					if (found)
  55. 						break;
  56. 				}
  57. 				if (found)
  58. 					break;
  59. 			}
  60.  
  61. 		}
  62. 	}
  63. 	/// pruning support 
  64. 	for (t = unique_support.begin(); t != unique_support.end(); ) {
  65. 		if (t->second < min_support) {
  66. 			loop = t;
  67. 			unique_events.erase(t->first);
  68. 			t++;
  69. 			unique_support.erase(loop); // if support < min_support , delete from the map
  70.  
  71. 		}
  72. 		else
  73. 			t++;
  74.  
  75. 	}
  76.  
  77.  
  78. 	////// CANDIDATE GENERATION OF SIZE 2
  79. 	set<string> candidatesSize2;
  80. 	//string candidatesSize2[100];
  81. 	set<char> ::iterator item1;
  82. 	set<char> ::iterator item2;
  83. 	int i = 0;
  84. 	for (item1 = unique_events.begin(); item1 != unique_events.end(); item1++) {
  85. 		for (item2 = unique_events.begin(); item2 != unique_events.end(); item2++) {
  86. 			string a, b;
  87. 			a.append(1, *item1);
  88. 			b.append(1, *item2);
  89. 			string h = a + ' '+ b;
  90.  
  91. 			candidatesSize2.insert(h);			
  92. 		}
  93. 	}
  94.  
  95. 	for (item1 = unique_events.begin(); item1 != unique_events.end(); item1++) {
  96. 		it = item1;
  97. 		for (item2 = ++it; item2 != unique_events.end(); item2++) {
  98. 			//cout << *it << endl;
  99. 			//cout << *item1 << " " << *item2 << endl;
  100. 			string a, b;
  101. 			a.append(1, *item1);
  102. 			b.append(1, *item2);
  103. 			string h = a + b;
  104.  
  105. 			candidatesSize2.insert(h);
  106. 		}
  107. 	}
  108.  
  109. 	*/
  110. 		set<string> ::iterator item11;
  111. 		set<string> ::iterator item22;
  112. 	set<string> candidatesSize3;
  113.  
  114. 	set<string> candidatesSize2;
  115. 				candidatesSize2.insert("b b");
  116. 				candidatesSize2.insert("a b");
  117. 				candidatesSize2.insert("b c");
  118. 				candidatesSize2.insert("c b");
  119. 				candidatesSize2.insert("bd");
  120. 				candidatesSize2.insert("d b");
  121. 				candidatesSize2.insert("b e");
  122. 				candidatesSize2.insert("d c");
  123.                 candidatesSize2.insert("ce");
  124.  
  125.  
  126.  
  127.  
  128.  
  129. 	for (item11 = candidatesSize2.begin(); item11 != candidatesSize2.end(); item11++) {
  130. 		for (item22 = candidatesSize2.begin(); item22 != candidatesSize2.end(); item22++) {
  131. 			string a, b, c;
  132. 			string i1=*item11,i2=*item22;
  133. 			if(i1==i2)
  134. 			continue;
  135. 			if (i1.size() == 3&& i2.size() == 3)
  136. 			{
  137. 				if (i1[2] == i2[0])
  138. 				{
  139. 					a.append(1, i1[0]);
  140. 					b.append(1, i2[0]);
  141. 					c.append(1, i2[2]);
  142. 					string h = a + ' ' + b + ' ' + c;
  143. 					candidatesSize3.insert(h);
  144.  
  145. 				}
  146. 			}
  147. 			else if (i1.size() == 3&& i2.size() == 2)
  148. 			{
  149. 				if (i1[2] == i2[0])
  150. 				{
  151. 					a.append(1, i1[0]);
  152. 					b.append(1, i2[0]);
  153. 					c.append(1, i2[1]);
  154. 					string h = a + ' ' + b  + c;
  155. 					candidatesSize3.insert(h);
  156.  
  157. 				}
  158. 			}
  159. 			else if (i1.size() == 2&& i2.size() == 3)
  160. 			{
  161. 				if (i1[1] == i2[0])
  162. 				{
  163. 					a.append(1, i1[0]);
  164. 					b.append(1, i2[0]);
  165. 					c.append(1, i2[2]);
  166. 					string h = a +  b + ' ' + c;
  167. 					candidatesSize3.insert(h);
  168.  
  169. 				}
  170. 			}
  171. 			else
  172. 			{
  173. 				if (i1[1] == i2[0])
  174. 				{
  175. 					a.append(1, i1[0]);
  176. 					b.append(1, i2[0]);
  177. 					c.append(1, i2[1]);
  178. 					string h = a +  b  + c;
  179. 					candidatesSize3.insert(h);
  180.  
  181. 				}
  182. 			}
  183.  
  184. 		}
  185. 	}
  186.  
  187. 	set<string> ::iterator sz;
  188. 	for (sz = candidatesSize3.begin(); sz != candidatesSize3.end(); sz++) {
  189. 		cout << *sz << endl;
  190. 	}
  191. 	set<string> ::iterator item3;
  192. 	//	set<string>  c1=candidatesSize3.begin();
  193. 		set<string> it1 = candidatesSize3;
  194. 		//set<string>  c2=candidatesSize3.end();
  195. 	   // string::iterator it2 = candidatesSize3.end();
  196.  
  197.  
  198. for (item3= it1.begin(); item3 != it1.end(); item3++) 
  199. {
  200. 	string a, b, c;
  201. 	string s = *item3;
  202. 	if(s.size()==5)//A B C
  203. 	{
  204. 			        a.append(1, s[0]);
  205. 					b.append(1, s[2]);
  206. 					c.append(1, s[4]);
  207.  
  208. 		string subseq1=a+' '+b;
  209. 		string subseq2=b+' '+c;
  210. 		string subseq3=a+' '+c;
  211.  
  212. 	 bool is_in = (candidatesSize2.find(subseq1) != candidatesSize2.end())&&
  213. 	 (candidatesSize2.find(subseq2) != candidatesSize2.end())&&
  214. 	  (candidatesSize2.find(subseq3) != candidatesSize2.end());
  215.  
  216. 	if(!is_in)
  217. 	{
  218. 		candidatesSize3.erase(candidatesSize3.find(s));
  219.  
  220. 	}
  221. 	}
  222. 	else if (s.size()==4)
  223. 	{
  224.  
  225.  
  226.  
  227. 		 if(s[2]==' ') //AB C
  228. 		{
  229. 			a.append(1, s[0]);
  230. 					b.append(1, s[1]);
  231. 					c.append(1, s[3]);
  232. 		string subseq1=a+b;
  233. 		string subseq2=b+' '+c;
  234. 		string subseq3=a+' '+c;
  235.  
  236. 	 bool is_in = (candidatesSize2.find(subseq1) != candidatesSize2.end())&&
  237. 	 (candidatesSize2.find(subseq2) != candidatesSize2.end())&&
  238. 	  (candidatesSize2.find(subseq3) != candidatesSize2.end());
  239.  
  240. 	if(!is_in)
  241. 		candidatesSize3.erase(candidatesSize3.find(s));
  242. 	}
  243.  if(s[1]==' ')//A BC
  244. 		{
  245. 			        a.append(1, s[0]);
  246. 					b.append(1, s[2]);
  247. 					c.append(1, s[3]);
  248. 			string subseq1=a+' '+b;
  249. 		     string subseq2= b + c ;
  250. 	           	string subseq3=a +' '+c;
  251.  
  252. 	          bool is_in = (candidatesSize2.find(subseq1) != candidatesSize2.end())&&
  253. 	 (candidatesSize2.find(subseq2) != candidatesSize2.end())&&
  254. 	  (candidatesSize2.find(subseq3) != candidatesSize2.end());
  255.  
  256.         	if(!is_in)
  257. 		 candidatesSize3.erase(candidatesSize3.find(s));
  258. 	     }
  259. 	}
  260. 	else //ABC
  261. 	{
  262. 		a.append(1, s[0]);
  263. 					b.append(1, s[1]);
  264. 					c.append(1, s[2]);
  265. 		string subseq1=a+b;
  266. 		string subseq2=b+c;
  267. 		string subseq3=a+c;
  268.  
  269. 	 bool is_in = (candidatesSize2.find(subseq1) != candidatesSize2.end())&&
  270. 	 (candidatesSize2.find(subseq2) != candidatesSize2.end())&&
  271. 	  (candidatesSize2.find(subseq3) != candidatesSize2.end());
  272.  
  273. 	if(!is_in)
  274. 		candidatesSize3.erase(candidatesSize3.find(s));
  275. 	}
  276.  
  277.  
  278.  
  279.  
  280. }
  281.  
  282. cout<<"-------------------------------------"<<endl;
  283. 		set<string> ::iterator sz1;
  284. 	for (sz1 = candidatesSize3.begin(); sz1 != candidatesSize3.end(); sz1++) {
  285. 		cout << *sz1 << endl;
  286. 	}
  287. 	return 0;
  288. }
Success #stdin #stdout 0.01s 5408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
a b b
a b c
a b e
a bd
b b c
b b e
b bd
b c b
b ce
bd b
bd c
c b b
c b c
c b e
c bd
d b b
d b c
d b e
d bd
d c b
d ce
-------------------------------------
a b b
b b c
b b e
b c b
b ce
bd b
bd c
c b b
d b b
d b c
d c b
https://ideone.com/eaT4CT
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!