#include <iostream>
#include <map>
#include <set>
#include<algorithm>
#include <iterator>
using namespace std;
int main( ) {
// your code goes here
string data[ 5 ] [ 5 ] = { { "A" ,"B" ,"FG" ,"C" ,"D" } ,
{ "B" ,"G" ,"D" } ,
{ "B" ,"F" ,"G" ,"AB" } ,
{ "F" ,"AB" ,"C" ,"D" } ,
{ "A" ,"BC" ,"G" ,"F" ,"DE" }
} ;
int min_support = 2 ;
set< char > unique_events; // sets hold unique values
map< char , int > unique_support; // map each unique value to it's support
for ( int row = 0 ; row < 5 ; row++ ) {
for ( int col = 0 ; col < 5 ; col++ ) {
for ( int s = 0 ; s < data[ row] [ col] .length ( ) ; s++ ) {
// looping over the dataset to insert unique events into the set
unique_events.insert ( data[ row] [ col] [ s] ) ;
}
}
}
set< char > :: iterator it;
map< char , int > :: iterator t;
map< char , int > :: iterator loop;
// iterating over each event in the set comparing it to the row in the dataset
// (whether it appeared n the row or not) if yes, break from that row incrementing it's support
// in the map
for ( it = unique_events.begin ( ) ; it ! = unique_events.end ( ) ; it++ ) {
for ( int row = 0 ; row < 5 ; row++ ) {
bool found = false ;
for ( int col = 0 ; col < 5 ; col++ ) {
for ( int s = 0 ; s < data[ row] [ col] .length ( ) ; s++ ) {
if ( * it == data[ row] [ col] [ s] ) {
//searching for the event in the map exists or not
t = unique_support.find ( data[ row] [ col] [ s] ) ;
if ( t ! = unique_support.end ( ) )
t- > second++ ;
else
unique_support.insert ( pair< char ,int > ( data[ row] [ col] [ s] ,1 ) ) ;
found = true ;
}
if ( found)
break ;
}
if ( found)
break ;
}
}
}
/// pruning support
for ( t = unique_support.begin ( ) ; t ! = unique_support.end ( ) ; ) {
if ( t- > second < min_support) {
loop = t;
unique_events.erase ( t- > first) ;
t++ ;
unique_support.erase ( loop) ; // if support < min_support , delete from the map
}
else
t++ ;
}
////// CANDIDATE GENERATION OF SIZE 2
set< string> candidatesSize2;
//string candidatesSize2[100];
set< char > :: iterator item1;
set< char > :: iterator item2;
int i = 0 ;
for ( item1 = unique_events.begin ( ) ; item1 ! = unique_events.end ( ) ; item1++ ) {
for ( item2 = unique_events.begin ( ) ; item2 ! = unique_events.end ( ) ; item2++ ) {
string a, b;
a.append ( 1 , * item1) ;
b.append ( 1 , * item2) ;
string h = a + ' ' + b;
candidatesSize2.insert ( h) ;
}
}
for ( item1 = unique_events.begin ( ) ; item1 ! = unique_events.end ( ) ; item1++ ) {
it = item1;
for ( item2 = ++ it; item2 ! = unique_events.end ( ) ; item2++ ) {
//cout << *it << endl;
//cout << *item1 << " " << *item2 << endl;
string a, b;
a.append ( 1 , * item1) ;
b.append ( 1 , * item2) ;
string h = a + b;
candidatesSize2.insert ( h) ;
}
}
set< string> :: iterator item11;
set< string> :: iterator item22;
// set<string> candidatesSize2;
set< string> candidatesSize3;
for ( item11 = candidatesSize2.begin ( ) ; item11 ! = candidatesSize2.end ( ) ; item11++ ) {
for ( item22 = candidatesSize2.begin ( ) ; item22 ! = candidatesSize2.end ( ) ; item22++ ) {
string a, b, c;
string i1= * item11,i2= * item22;
if ( i1.size ( ) == 3 && i2.size ( ) == 3 )
{
if ( i1[ i1.size ( ) - 1 ] == i2[ 0 ] )
{
a.append ( 1 , i1[ 0 ] ) ;
b.append ( 1 , i2[ 0 ] ) ;
c.append ( 1 , i2[ i2.size ( ) - 1 ] ) ;
string h = a + ' ' + b + ' ' + c;
candidatesSize3.insert ( h) ;
}
}
/* else if (item11.length() == 3 && item22.length() == 2)
{
if (item11[item11.length() - 1] == item22[0])
{
a.append(1, *item11[0]);
b.append(1, *item22[0]);
c.append(1, *item22[item22.length() - 1]);
string h = a + ' ' + b + c;
candidatesSize3.insert(h);
}
}
else if (item11.length() == 2 && item22.length() == 3)
{
if (item11[item11.length() - 1] == item22[0])
{
a.append(1, *item11[0]);
b.append(1, *item22[0]);
c.append(1, *item22[item22.length() - 1]);
string h = a + b +' ' + c;
candidatesSize3.insert(h);
}
}
else
{
if (item11[item11.length() - 1] == item22[0])
{
a.append(1, *item11[0]);
b.append(1, *item22[0]);
c.append(1, *item22[item22.length() - 1]);
string h = a + b + c;
candidatesSize3.insert(h);
}
}*/
}
}
set< string> :: iterator sz;
for ( sz = candidatesSize3.begin ( ) ; sz ! = candidatesSize3.end ( ) ; sz++ ) {
cout << * sz << endl;
}
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlIDxpdGVyYXRvcj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJCglzdHJpbmcgZGF0YVs1XVs1XSA9IHsgICB7IkEiLCJCIiwiRkciLCJDIiwiRCJ9ICwKCQkJCQkJCXsiQiIsIkciLCJEIn0sCgkJCQkJCQl7IkIiLCJGIiwiRyIsIkFCIn0sCgkJCQkJCQl7IkYiLCJBQiIsIkMiLCJEIn0sCgkJCQkJCQl7IkEiLCJCQyIsIkciLCJGIiwiREUifQoJfTsKCWludCBtaW5fc3VwcG9ydCA9IDI7CglzZXQ8Y2hhcj4gdW5pcXVlX2V2ZW50czsgLy8gc2V0cyBob2xkIHVuaXF1ZSB2YWx1ZXMKCW1hcDxjaGFyLCBpbnQ+IHVuaXF1ZV9zdXBwb3J0OyAvLyBtYXAgZWFjaCB1bmlxdWUgdmFsdWUgdG8gaXQncyBzdXBwb3J0CgkKCWZvciAoaW50IHJvdyA9IDA7IHJvdyA8IDU7IHJvdysrKSB7CgkJZm9yIChpbnQgY29sID0gMDsgY29sIDwgNTsgY29sKyspIHsKCQkJZm9yIChpbnQgcyA9IDA7IHMgPCBkYXRhW3Jvd11bY29sXS5sZW5ndGgoKTsgcysrKSB7CgkJCQkvLyBsb29waW5nIG92ZXIgdGhlIGRhdGFzZXQgdG8gaW5zZXJ0IHVuaXF1ZSBldmVudHMgaW50byB0aGUgc2V0CgkJCQl1bmlxdWVfZXZlbnRzLmluc2VydChkYXRhW3Jvd11bY29sXVtzXSk7CgkJCX0KCQl9Cgl9CgoJc2V0PGNoYXI+IDo6aXRlcmF0b3IgaXQ7CgltYXA8Y2hhciwgaW50PiA6Oml0ZXJhdG9yIHQ7CgltYXA8Y2hhciwgaW50PiA6Oml0ZXJhdG9yIGxvb3A7CgkKCS8vIGl0ZXJhdGluZyBvdmVyIGVhY2ggZXZlbnQgaW4gdGhlIHNldCBjb21wYXJpbmcgaXQgdG8gdGhlIHJvdyBpbiB0aGUgZGF0YXNldCAKCS8vICh3aGV0aGVyIGl0IGFwcGVhcmVkIG4gdGhlIHJvdyBvciBub3QpIGlmIHllcywgYnJlYWsgZnJvbSB0aGF0IHJvdyBpbmNyZW1lbnRpbmcgaXQncyBzdXBwb3J0IAoJLy8gaW4gdGhlIG1hcAoJZm9yIChpdCA9IHVuaXF1ZV9ldmVudHMuYmVnaW4oKTsgaXQgIT0gdW5pcXVlX2V2ZW50cy5lbmQoKTsgaXQrKykgewoJCWZvciAoaW50IHJvdyA9IDA7IHJvdyA8IDU7IHJvdysrKSB7CgoJCQlib29sIGZvdW5kID0gZmFsc2U7CgoJCQlmb3IgKGludCBjb2wgPSAwOyBjb2wgPCA1OyBjb2wrKykgewoJCQkJZm9yIChpbnQgcyA9IDA7IHMgPCBkYXRhW3Jvd11bY29sXS5sZW5ndGgoKTsgcysrKSB7CgoJCQkJCWlmICgqaXQgPT0gZGF0YVtyb3ddW2NvbF1bc10pIHsKCQkJCQkJLy9zZWFyY2hpbmcgZm9yIHRoZSBldmVudCBpbiB0aGUgbWFwIGV4aXN0cyBvciBub3QKCQkJCQkJdCA9IHVuaXF1ZV9zdXBwb3J0LmZpbmQoZGF0YVtyb3ddW2NvbF1bc10pOwoJCQkJCQlpZiAodCAhPSB1bmlxdWVfc3VwcG9ydC5lbmQoKSkKCQkJCQkJCXQtPnNlY29uZCsrOwoJCQkJCQllbHNlCQkJCQkKCQkJCQkJCXVuaXF1ZV9zdXBwb3J0Lmluc2VydChwYWlyPGNoYXIsaW50PihkYXRhW3Jvd11bY29sXVtzXSwxKSk7CgkJCQkJCWZvdW5kID0gdHJ1ZTsKCQkJCQl9CgkJCQkJaWYgKGZvdW5kKQoJCQkJCQlicmVhazsKCQkJCX0KCQkJCWlmIChmb3VuZCkKCQkJCQlicmVhazsKCQkJfQoJCQkKCQl9Cgl9CgkvLy8gcHJ1bmluZyBzdXBwb3J0IAoJZm9yICh0ID0gdW5pcXVlX3N1cHBvcnQuYmVnaW4oKTsgdCAhPSB1bmlxdWVfc3VwcG9ydC5lbmQoKTsgKSB7CgkJaWYgKHQtPnNlY29uZCA8IG1pbl9zdXBwb3J0KSB7CgkJCWxvb3AgPSB0OwoJCQl1bmlxdWVfZXZlbnRzLmVyYXNlKHQtPmZpcnN0KTsKCQkJdCsrOwoJCQl1bmlxdWVfc3VwcG9ydC5lcmFzZShsb29wKTsgLy8gaWYgc3VwcG9ydCA8IG1pbl9zdXBwb3J0ICwgZGVsZXRlIGZyb20gdGhlIG1hcAoJCQkKCQl9CgkJZWxzZQoJCQl0Kys7CgkJCQoJfQoJCgkKCS8vLy8vLyBDQU5ESURBVEUgR0VORVJBVElPTiBPRiBTSVpFIDIKCXNldDxzdHJpbmc+IGNhbmRpZGF0ZXNTaXplMjsKCS8vc3RyaW5nIGNhbmRpZGF0ZXNTaXplMlsxMDBdOwoJc2V0PGNoYXI+IDo6aXRlcmF0b3IgaXRlbTE7CglzZXQ8Y2hhcj4gOjppdGVyYXRvciBpdGVtMjsKCWludCBpID0gMDsKCWZvciAoaXRlbTEgPSB1bmlxdWVfZXZlbnRzLmJlZ2luKCk7IGl0ZW0xICE9IHVuaXF1ZV9ldmVudHMuZW5kKCk7IGl0ZW0xKyspIHsKCQlmb3IgKGl0ZW0yID0gdW5pcXVlX2V2ZW50cy5iZWdpbigpOyBpdGVtMiAhPSB1bmlxdWVfZXZlbnRzLmVuZCgpOyBpdGVtMisrKSB7CgkJCXN0cmluZyBhLCBiOwoJCQlhLmFwcGVuZCgxLCAqaXRlbTEpOwoJCQliLmFwcGVuZCgxLCAqaXRlbTIpOwoJCQlzdHJpbmcgaCA9IGEgKyAnICcrIGI7CgkJCQoJCQljYW5kaWRhdGVzU2l6ZTIuaW5zZXJ0KGgpOwkJCQoJCX0KCX0KCglmb3IgKGl0ZW0xID0gdW5pcXVlX2V2ZW50cy5iZWdpbigpOyBpdGVtMSAhPSB1bmlxdWVfZXZlbnRzLmVuZCgpOyBpdGVtMSsrKSB7CgkJaXQgPSBpdGVtMTsKCQlmb3IgKGl0ZW0yID0gKytpdDsgaXRlbTIgIT0gdW5pcXVlX2V2ZW50cy5lbmQoKTsgaXRlbTIrKykgewoJCQkvL2NvdXQgPDwgKml0IDw8IGVuZGw7CgkJCS8vY291dCA8PCAqaXRlbTEgPDwgIiAiIDw8ICppdGVtMiA8PCBlbmRsOwoJCQlzdHJpbmcgYSwgYjsKCQkJYS5hcHBlbmQoMSwgKml0ZW0xKTsKCQkJYi5hcHBlbmQoMSwgKml0ZW0yKTsKCQkJc3RyaW5nIGggPSBhICsgYjsKCgkJCWNhbmRpZGF0ZXNTaXplMi5pbnNlcnQoaCk7CgkJfQoJfQoJCXNldDxzdHJpbmc+IDo6aXRlcmF0b3IgaXRlbTExOwoJCXNldDxzdHJpbmc+IDo6aXRlcmF0b3IgaXRlbTIyOwovLwlzZXQ8c3RyaW5nPiBjYW5kaWRhdGVzU2l6ZTI7CglzZXQ8c3RyaW5nPiBjYW5kaWRhdGVzU2l6ZTM7CgkKCQoJZm9yIChpdGVtMTEgPSBjYW5kaWRhdGVzU2l6ZTIuYmVnaW4oKTsgaXRlbTExICE9IGNhbmRpZGF0ZXNTaXplMi5lbmQoKTsgaXRlbTExKyspIHsKCQlmb3IgKGl0ZW0yMiA9IGNhbmRpZGF0ZXNTaXplMi5iZWdpbigpOyBpdGVtMjIgIT0gY2FuZGlkYXRlc1NpemUyLmVuZCgpOyBpdGVtMjIrKykgewoJCQlzdHJpbmcgYSwgYiwgYzsKCQkJc3RyaW5nIGkxPSppdGVtMTEsaTI9Kml0ZW0yMjsKCQkJaWYgKGkxLnNpemUoKSA9PSAzJiYgaTIuc2l6ZSgpID09IDMpCgkJCXsKCQkJCWlmIChpMVtpMS5zaXplKCkgLSAxXSA9PSBpMlswXSkKCQkJCXsKCQkJCQlhLmFwcGVuZCgxLCBpMVswXSk7CgkJCQkJYi5hcHBlbmQoMSwgaTJbMF0pOwoJCQkJCWMuYXBwZW5kKDEsIGkyW2kyLnNpemUoKSAtIDFdKTsKCQkJCQlzdHJpbmcgaCA9IGEgKyAnICcgKyBiICsgJyAnICsgYzsKCQkJCQljYW5kaWRhdGVzU2l6ZTMuaW5zZXJ0KGgpOwoKCQkJCX0KCQkJfQoJCS8qCWVsc2UgaWYgKGl0ZW0xMS5sZW5ndGgoKSA9PSAzICYmIGl0ZW0yMi5sZW5ndGgoKSA9PSAyKQoJCQl7CgkJCQlpZiAoaXRlbTExW2l0ZW0xMS5sZW5ndGgoKSAtIDFdID09IGl0ZW0yMlswXSkKCQkJCXsKCQkJCQlhLmFwcGVuZCgxLCAqaXRlbTExWzBdKTsKCQkJCQliLmFwcGVuZCgxLCAqaXRlbTIyWzBdKTsKCQkJCQljLmFwcGVuZCgxLCAqaXRlbTIyW2l0ZW0yMi5sZW5ndGgoKSAtIDFdKTsKCQkJCQlzdHJpbmcgaCA9IGEgKyAnICcgKyBiICsgYzsKCQkJCQljYW5kaWRhdGVzU2l6ZTMuaW5zZXJ0KGgpOwoKCQkJCX0KCQkJfQoJCQllbHNlIGlmIChpdGVtMTEubGVuZ3RoKCkgPT0gMiAmJiBpdGVtMjIubGVuZ3RoKCkgPT0gMykKCQkJewoJCQkJaWYgKGl0ZW0xMVtpdGVtMTEubGVuZ3RoKCkgLSAxXSA9PSBpdGVtMjJbMF0pCgkJCQl7CgkJCQkJYS5hcHBlbmQoMSwgKml0ZW0xMVswXSk7CgkJCQkJYi5hcHBlbmQoMSwgKml0ZW0yMlswXSk7CgkJCQkJYy5hcHBlbmQoMSwgKml0ZW0yMltpdGVtMjIubGVuZ3RoKCkgLSAxXSk7CgkJCQkJc3RyaW5nIGggPSBhICArIGIgKycgJyArIGM7CgkJCQkJY2FuZGlkYXRlc1NpemUzLmluc2VydChoKTsKCgkJCQl9CgkJCX0KCQkJZWxzZQoJCQl7CgkJCQlpZiAoaXRlbTExW2l0ZW0xMS5sZW5ndGgoKSAtIDFdID09IGl0ZW0yMlswXSkKCQkJCXsKCQkJCQlhLmFwcGVuZCgxLCAqaXRlbTExWzBdKTsKCQkJCQliLmFwcGVuZCgxLCAqaXRlbTIyWzBdKTsKCQkJCQljLmFwcGVuZCgxLCAqaXRlbTIyW2l0ZW0yMi5sZW5ndGgoKSAtIDFdKTsKCQkJCQlzdHJpbmcgaCA9IGEgICsgYiArIGM7CgkJCSAgICAgICAgY2FuZGlkYXRlc1NpemUzLmluc2VydChoKTsKCQkJCX0KCQkJfSovCgoJCX0KCX0KCglzZXQ8c3RyaW5nPiA6Oml0ZXJhdG9yIHN6OwoJZm9yIChzeiA9IGNhbmRpZGF0ZXNTaXplMy5iZWdpbigpOyBzeiAhPSBjYW5kaWRhdGVzU2l6ZTMuZW5kKCk7IHN6KyspIHsKCQljb3V0IDw8ICpzeiA8PCBlbmRsOwoJfQoKCQoJcmV0dXJuIDA7Cn0=