fork(1) download
  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. set<string> ::iterator item11;
  109. set<string> ::iterator item22;
  110. // set<string> candidatesSize2;
  111. set<string> candidatesSize3;
  112.  
  113.  
  114. for (item11 = candidatesSize2.begin(); item11 != candidatesSize2.end(); item11++) {
  115. for (item22 = candidatesSize2.begin(); item22 != candidatesSize2.end(); item22++) {
  116. string a, b, c;
  117. string i1=*item11,i2=*item22;
  118. if (i1.size() == 3&& i2.size() == 3)
  119. {
  120. if (i1[i1.size() - 1] == i2[0])
  121. {
  122. a.append(1, i1[0]);
  123. b.append(1, i2[0]);
  124. c.append(1, i2[i2.size() - 1]);
  125. string h = a + ' ' + b + ' ' + c;
  126. candidatesSize3.insert(h);
  127.  
  128. }
  129. }
  130. else if (i1.size() == 3&& i2.size() == 2)
  131. {
  132. if (i1[i1.size() - 1] == i2[0])
  133. {
  134. a.append(1, i1[0]);
  135. b.append(1, i2[0]);
  136. c.append(1, i2[i2.size() - 1]);
  137. string h = a + ' ' + b + c;
  138. candidatesSize3.insert(h);
  139.  
  140. }
  141. }
  142. else if (i1.size() == 2&& i2.size() == 3)
  143. {
  144. if (i1[i1.size() - 1] == i2[0])
  145. {
  146. a.append(1, i1[0]);
  147. b.append(1, i2[0]);
  148. c.append(1, i2[i2.size() - 1]);
  149. string h = a + b + ' ' + c;
  150. candidatesSize3.insert(h);
  151.  
  152. }
  153. }
  154. else
  155. {
  156. if (i1[i1.size() - 1] == i2[0])
  157. {
  158. a.append(1, i1[0]);
  159. b.append(1, i2[0]);
  160. c.append(1, i2[i2.size() - 1]);
  161. string h = a + b + c;
  162. candidatesSize3.insert(h);
  163.  
  164. }
  165. }
  166.  
  167. }
  168. }
  169.  
  170. set<string> ::iterator sz;
  171. for (sz = candidatesSize3.begin(); sz != candidatesSize3.end(); sz++) {
  172. cout << *sz << endl;
  173. }
  174.  
  175.  
  176. return 0;
  177. }
Success #stdin #stdout 0.01s 5528KB
stdin
Standard input is empty
stdout
A A A
A A B
A A C
A A D
A A F
A A G
A AB
A AC
A AD
A AF
A AG
A B A
A B B
A B C
A B D
A B F
A B G
A BC
A BD
A BF
A BG
A C A
A C B
A C C
A C D
A C F
A C G
A CD
A CF
A CG
A D A
A D B
A D C
A D D
A D F
A D G
A DF
A DG
A F A
A F B
A F C
A F D
A F F
A F G
A FG
A G A
A G B
A G C
A G D
A G F
A G G
AB A
AB B
AB C
AB D
AB F
AB G
ABC
ABD
ABF
ABG
AC A
AC B
AC C
AC D
AC F
AC G
ACD
ACF
ACG
AD A
AD B
AD C
AD D
AD F
AD G
ADF
ADG
AF A
AF B
AF C
AF D
AF F
AF G
AFG
AG A
AG B
AG C
AG D
AG F
AG G
B A A
B A B
B A C
B A D
B A F
B A G
B AB
B AC
B AD
B AF
B AG
B B A
B B B
B B C
B B D
B B F
B B G
B BC
B BD
B BF
B BG
B C A
B C B
B C C
B C D
B C F
B C G
B CD
B CF
B CG
B D A
B D B
B D C
B D D
B D F
B D G
B DF
B DG
B F A
B F B
B F C
B F D
B F F
B F G
B FG
B G A
B G B
B G C
B G D
B G F
B G G
BC A
BC B
BC C
BC D
BC F
BC G
BCD
BCF
BCG
BD A
BD B
BD C
BD D
BD F
BD G
BDF
BDG
BF A
BF B
BF C
BF D
BF F
BF G
BFG
BG A
BG B
BG C
BG D
BG F
BG G
C A A
C A B
C A C
C A D
C A F
C A G
C AB
C AC
C AD
C AF
C AG
C B A
C B B
C B C
C B D
C B F
C B G
C BC
C BD
C BF
C BG
C C A
C C B
C C C
C C D
C C F
C C G
C CD
C CF
C CG
C D A
C D B
C D C
C D D
C D F
C D G
C DF
C DG
C F A
C F B
C F C
C F D
C F F
C F G
C FG
C G A
C G B
C G C
C G D
C G F
C G G
CD A
CD B
CD C
CD D
CD F
CD G
CDF
CDG
CF A
CF B
CF C
CF D
CF F
CF G
CFG
CG A
CG B
CG C
CG D
CG F
CG G
D A A
D A B
D A C
D A D
D A F
D A G
D AB
D AC
D AD
D AF
D AG
D B A
D B B
D B C
D B D
D B F
D B G
D BC
D BD
D BF
D BG
D C A
D C B
D C C
D C D
D C F
D C G
D CD
D CF
D CG
D D A
D D B
D D C
D D D
D D F
D D G
D DF
D DG
D F A
D F B
D F C
D F D
D F F
D F G
D FG
D G A
D G B
D G C
D G D
D G F
D G G
DF A
DF B
DF C
DF D
DF F
DF G
DFG
DG A
DG B
DG C
DG D
DG F
DG G
F A A
F A B
F A C
F A D
F A F
F A G
F AB
F AC
F AD
F AF
F AG
F B A
F B B
F B C
F B D
F B F
F B G
F BC
F BD
F BF
F BG
F C A
F C B
F C C
F C D
F C F
F C G
F CD
F CF
F CG
F D A
F D B
F D C
F D D
F D F
F D G
F DF
F DG
F F A
F F B
F F C
F F D
F F F
F F G
F FG
F G A
F G B
F G C
F G D
F G F
F G G
FG A
FG B
FG C
FG D
FG F
FG G
G A A
G A B
G A C
G A D
G A F
G A G
G AB
G AC
G AD
G AF
G AG
G B A
G B B
G B C
G B D
G B F
G B G
G BC
G BD
G BF
G BG
G C A
G C B
G C C
G C D
G C F
G C G
G CD
G CF
G CG
G D A
G D B
G D C
G D D
G D F
G D G
G DF
G DG
G F A
G F B
G F C
G F D
G F F
G F G
G FG
G G A
G G B
G G C
G G D
G G F
G G G