fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4. using namespace std;
  5.  
  6. /*
  7. level 1 = 3 unique: {1,2,3} = 1 tuple
  8. level 2 = 4 unique: {1,2,3} {1,2,4} + {1,3,4} + 1 = 3 + 1 = 4 tuples
  9. level 3 = 5 unique: {1,2,3} {1,2,4} {1,2,5} + {1,3,4} {1,3,5} + {1,4,5} + 4 = 10 tuples
  10. level 4 = 6 unique: {1,2,3} {1,2,4} {1,2,5} {1,2,6} + {1,3,4} {1,3,5} {1,3,6} {1,4,5} {1,4,6} {1,5,6} + 10 = 20
  11. */
  12.  
  13. typedef vector<int> Triplet;
  14.  
  15. int getSumSequence(int n)
  16. {
  17. 	if (n <= 0)
  18. 		return 0;
  19.  
  20. 	return n + getSumSequence(n - 1);
  21. }
  22.  
  23. int countTriplets(int index, int unique)
  24. {
  25. 	int level = unique - index  - 2;
  26.  
  27. 	if (level < 1)
  28. 		return 0;
  29.  
  30. 	if (level == 1)
  31. 		return 1;
  32.  
  33. 	return getSumSequence(level);
  34. }
  35.  
  36. //BFS approach
  37. void countTriplets(const int * arr, int length, vector<Triplet*>& triplets)
  38. {
  39. 	//first count number of unique elements to avoid duplicates
  40. 	int unique = 1;
  41. 	for (int i = 1; i < length; ++i)
  42. 	{
  43. 		if (arr[i - 1] != arr[i])
  44. 			unique++;
  45. 	}
  46.  
  47. 	deque<Triplet*> constructed;
  48.  
  49. 	int nConstructed = countTriplets(0, unique);
  50. 	int elementID = 0;
  51.  
  52. 	for (int i = 0; i < length; ++i)
  53. 	{
  54. 		//skip doubles
  55. 		if (i > 0 && arr[i - 1] == arr[i])
  56. 			continue;		
  57.  
  58. 		//Add new tuples to deque on this level
  59. 		int nTriplets = countTriplets(elementID++, unique);
  60. 		for (int t = 0; t < nTriplets; ++t)
  61. 		{
  62. 			Triplet *triplet = new Triplet();
  63. 			constructed.push_front(triplet);
  64. 		}
  65.  
  66. 		//Process existing tuples in deque by adding arr[i] to the first nConstructed elements
  67. 		//if tuple has 3 elements pop it and add it to result
  68. 		for (int t = 0; t < nConstructed; ++t)
  69. 		{
  70. 			Triplet *first = constructed.front();
  71.  
  72. 			first->push_back(arr[i]);
  73. 			if (first->size() == 3)
  74. 			{
  75. 				triplets.push_back(first); //if triplet is completed add it to triplets
  76. 			}
  77. 			else
  78. 			{
  79. 				constructed.push_back(first); //otherwise keep it in constructed
  80. 			}
  81. 			constructed.pop_front();
  82. 		}
  83. 	}
  84. }
  85.  
  86. int main()
  87. {
  88. 	int * arr = new int[7] { 1, 1, 2, 2, 3, 4, 5 };
  89. 	vector<Triplet*> triplets;
  90. 	countTriplets(arr, 7, triplets);
  91.  
  92. 	for (auto triplet : triplets)
  93. 	{
  94. 		cout << "{ ";
  95. 		for (int i : *triplet)
  96. 		{
  97. 			cout << i << " ";
  98. 		}
  99. 		cout << "} ";
  100.  
  101. 		delete triplet;
  102. 	}
  103.  
  104. 	return 0;
  105. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{ 1 2 4 } { 1 2 4 } { 1 2 4 } { 1 3 4 } { 1 3 5 } { 1 3 5 } { 2 3 5 } { 2 3 5 } { 2 4 5 } { 3 4 5 }
https://ideone.com/SQ4SKA
language:
C++14 (gcc 8.3)
created:
9 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!