fork download
copy 
  1.  
  2. #include <iostream> 
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<string.h>
  6. #include <fstream>
  7. #include <strstream>
  8. #include <sstream>
  9. #include <utility>
  10. #include <map>
  11. #include <list>
  12. #include <set>
  13. #include <vector>
  14. #include <iomanip>
  15. #include <algorithm>
  16. #include <iterator>
  17. using namespace std;
  18.  
  19. int threshold = 3;
  20. std::map <int, set<int>> Ls;
  21. std::size_t Msize = 0, temp = 0;
  22. std::size_t MCsize=0, temp2 = 0;
  23.  
  24. template <typename Iterator>
  25. inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
  26. {
  27. /* Credits: Thomas Draper */
  28. if ((first == last) || (first == k) || (last == k))
  29. return false;
  30. Iterator itr1 = first;
  31. Iterator itr2 = last;
  32. ++itr1;
  33. if (last == itr1)
  34. return false;
  35. itr1 = last;
  36. --itr1;
  37. itr1 = k;
  38. --itr2;
  39. while (first != itr1)
  40. {
  41. if (*--itr1 < *itr2)
  42. {
  43. Iterator j = k;
  44. while (!(*itr1 < *j)) ++j;
  45. std::iter_swap(itr1, j);
  46. ++itr1;
  47. ++j;
  48. itr2 = k;
  49. std::rotate(itr1, j, last);
  50. while (last != j)
  51. {
  52. ++j;
  53. ++itr2;
  54. }
  55. std::rotate(k, itr2, last);
  56. return true;
  57. }
  58. }
  59. std::rotate(first, k, last);
  60. return false;
  61. }
  62.  
  63.  
  64.  int main()
  65. {
  66. 	 std::vector<std::vector<int>> data =
  67. {
  68. {1, 2, 3, 4, 5},
  69. {1, 3, 4, 5},
  70. {1, 2, 3, 5},
  71. {1, 3}
  72. };
  73.  
  74. /*
  75. in my program, I calculte Msize as:
  76. Msize = std::distance(std::istream_iterator<std::string>(Sline1),
  77. 			std::istream_iterator<std::string>());
  78.  
  79. 		if (temp > Msize)
  80. 			Msize = temp;
  81. 		else
  82. 			temp = Msize;
  83. */
  84. Msize =5; 
  85. 	int j = 0;
  86. 	std::size_t k = 0;
  87. 	std::map<std::set<int>, int> counts;
  88.  
  89. 	for (std::size_t Lsize = 1; Lsize <= Msize; ++Lsize)
  90. 	{
  91. 		for (unsigned i = 0; i < data.size(); ++i)
  92. 		{
  93. 			//std::size_t k = std::min(Lsize, data[i].size());
  94. 			if (Lsize >  data[i].size())
  95. 				continue;
  96. 			else
  97. 				 k = Lsize;
  98.  
  99. 			do
  100. 			{
  101. 				std::set<int> n_k(data[i].begin(), data[i].begin() + k);
  102.  
  103. 				if (Ls.size() != 0)
  104. 				{
  105. 					std::map <int, set<int>> ::iterator ls2 = Ls.begin();
  106.  
  107. 					while (ls2 != Ls.end())
  108. 					{
  109. 						if (std::includes(n_k.begin(), n_k.end(), ls2->second.begin(), ls2->second.end()))
  110. 						{
  111. 							++j;
  112. 							Ls[j].insert(n_k.begin(), n_k.end());
  113. 							goto ncom;
  114. 						}
  115. 						else
  116. 						++ls2;
  117. 					}
  118. 				}
  119. 					++counts[n_k];
  120. 				ncom:
  121. 					cout << ""; // If I don't put this statement  I will get error: missing {
  122. 			} while (next_combination(data[i].begin(), data[i].begin() + k, data[i].end()));
  123.  
  124. 		}
  125.  
  126.  
  127. 		MCsize = counts.size();
  128. 		if (temp2 == MCsize) // check if counts don't have more supset > threshold, then no needs to generate  more superset
  129. 			goto stop;
  130. 		else
  131. 			temp2 = MCsize;
  132.  
  133. 		std::map<std::set<int>, int> ::iterator current = counts.begin();
  134.  
  135. 		while (current != counts.end())
  136. 		{
  137. 			if (current->second < threshold)
  138. 			{
  139. 				Ls[j].insert(current->first.begin(), current->first.end());
  140. 				current = counts.erase(current);
  141. 				++j;
  142. 			}
  143. 			else
  144. 				++current;
  145. 		}
  146.  
  147. 		}
  148.  
  149.  
  150. 	stop:
  151. 	for (const auto& p : counts)
  152. 	{
  153. 		std::cout << "{";
  154. 		for (auto e : p.first) {
  155. 			std::cout << e << " ";
  156. 		}
  157. 		std::cout << "} = " << p.second << std::endl;
  158. 	}
  159.  
  160.  
  161. 	data.clear();
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168. 	return 0;
  169. }
  170.  
  171.  
  172.  
  173.  
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{1 } = 4
{1 3 } = 4
{1 3 5 } = 3
{1 5 } = 3
{3 } = 4
{3 5 } = 3
{5 } = 3
https://ideone.com/kWCzTM
language:
C++14 (gcc 8.3)
created:
11 years 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!