#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>


struct Trans {
	int Item;
	float Prob;

};
/*std::istream& operator>>(std::istream &is, Trans &d)
{
	return is >> d.Item >> d.Prob ;
}*/




/*void ScanData()
{
	ifstream in;
	in.open("data.txt");

	std::string line;
	int i = 0;



	while (std::getline(in, line))
	{
		std::stringstream Sline1(line);
		std::stringstream ss(line);
		std::vector<Trans> inner;

		Msize = std::distance(std::istream_iterator<std::string>(Sline1),
			std::istream_iterator<std::string>());


		if (temp > Msize)
			Msize = temp;
		else
			temp = Msize;

		Trans info;

		while (ss >> info)
			inner.push_back(info);

		data.push_back(inner);



	}
}*/




template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
	/* Credits: Thomas Draper */
	if ((first == last) || (first == k) || (last == k))
		return false;
	Iterator itr1 = first;
	Iterator itr2 = last;
	++itr1;
	if (last == itr1)
		return false;
	itr1 = last;
	--itr1;
	itr1 = k;
	--itr2;
	while (first != itr1)
	{
		if (*--itr1 < *itr2)
		{
			Iterator j = k;
			while (!(*itr1 < *j)) ++j;
			std::iter_swap(itr1, j);
			++itr1;
			++j;
			itr2 = k;
			std::rotate(itr1, j, last);
			while (last != j)
			{
				++j;
				++itr2;
			}
			std::rotate(k, itr2, last);
			return true;
		}
	}
	std::rotate(first, k, last);
	return false;
}


int main()
{
	//ScanData();
int threshold = 3;

std::vector<std::vector<Trans>> data;

std::map <int, std::set <Trans>> Ls;

std::vector<Trans> inner1 = { { 1, 0.933 } ,
	{ 2, 0.865 }, { 3, 0.919 }, { 4, 0.726 }};
 
	std::vector<Trans> inner2 = { { 3, 0.906 },
	{ 2, 0.854 }, { 4, 0.726 } };

	std::vector<Trans> inner3 = { { 4, 0.865 },
	{ 3, 0.933 }, { 5, 0.919 } };


	data.push_back(inner1);
	data.push_back(inner2);
	data.push_back(inner3);

std::size_t Msize = 4;
std::size_t MCsize = 0, temp2 = 0;

	int j = 0;
	std::size_t k = 0;
	std::map<std::set<Trans>, int> counts;

	for (std::size_t Lsize = 1; Lsize <= Msize; ++Lsize)
	{
		for (unsigned i = 0; i < data.size(); ++i)
		{

			//std::size_t k = std::min(Lsize, data[i].size());
			if (Lsize >  data[i].size())
				continue;
			else
				k = Lsize;

			do
			{
				//std::vector<Trans>::iterator li = data[i].begin();

				std::set<Trans> n_k(data[i].begin(), data[i].begin() + k);

				// i wan to multiply all probabilities in n_k
				std::set<Trans> ::iterator it = n_k.begin();
				float Prob = 0;
				while (it != n_k.end())
				{
					Prob *= it->Prob;
					++it;
				}


				//	std::set<Trans> n_k(li->Item, li->Item);

				if (Ls.size() != 0)
				{
					std::map <int, std::set <Trans>> ::iterator ls2 = Ls.begin();

					while (ls2 != Ls.end())
					{
						if (std::includes(n_k.begin(), n_k.end(), ls2->second.begin(), ls2->second.end()))
						{
							++j;
							Ls[j].insert(n_k.begin(), n_k.end());
							goto ncom;
						}
						else
							++ls2;
					}
				}
				counts[n_k] += Prob;
			ncom:
				std::cout << ""; // If I don't put this statement  I will get error: missing {
			} while (next_combination(data[i].begin(), data[i].begin() + k, data[i].end()));
		}


		MCsize = counts.size();
		if (temp2 == MCsize) // check if counts don't have more supset > threshold, then no needs to generate  more superset
			goto stop;
		else
			temp2 = MCsize;

		std::map<std::set<Trans>, int> ::iterator current = counts.begin();

		while (current != counts.end())
		{
			if (current->second < threshold)
			{
				Ls[j].insert(current->first.begin(), current->first.end());
				current = counts.erase(current);
				++j;
			}
			else
				++current;
		}

	}

	
stop:
	/*	for (const auto& p : counts)
	{
	std::cout << "{";
	for (auto e : p.first) {
	std::cout << e << " ";
	}
	std::cout << "} = " << p.second << std::endl;
	}*/


	data.clear();





	return 0;
}