fork download
copy 
  1. #include <iostream>
  2. #include <iomanip> 
  3.  
  4. using namespace std;
  5.  
  6. class CombinationGeneratorException {};
  7.  
  8. class CombinationGenerator
  9. {
  10. private:
  11. 	int *_list;
  12. 	int *_stack;
  13. 	int _size;
  14. 	int _i, _j, _p, _c;
  15. 	int _all;
  16. 	CombinationGenerator();
  17. public:
  18. 	CombinationGenerator(int size)
  19. 			: _size(size), _i(1), _j(0), _p(0), _all(0), _c(0) {
  20. 		if (_size < 2) {
  21. 			throw CombinationGeneratorException();
  22. 		}
  23. 		_list = new int[_size];
  24. 		_stack = new int[_size];
  25. 	}
  26. 	~CombinationGenerator() {
  27. 		delete [] _list;
  28. 		delete [] _stack;
  29. 	}
  30.  
  31. 	void init(int size) {
  32. 		if (size < 2) {
  33. 			throw CombinationGeneratorException();
  34. 		}
  35. 		if (size > _size) {
  36. 			delete [] _list;
  37. 			delete [] _stack;
  38. 			_list = new int[size];
  39. 			_stack = new int[size];
  40. 		}
  41. 		_size = size;
  42. 		_all = 0;
  43. 		_i = 1;
  44. 		_j = _p = _c = 0;
  45. 	}
  46.  
  47. 	void reset() {
  48. 		for (_j = 0; _j < _size; _j++) {
  49. 			_list[_j] = 0;
  50. 		}
  51. 		_i = 1;
  52. 		_j = 0;
  53. 		_p = 0;
  54. 		_c = 0;
  55. 	}
  56.  
  57. 	int hasNext() {
  58. 		return _c != allpattern();
  59. 	}
  60.  
  61. 	const int* get(int idx) {
  62. 		if (idx < 1 || idx > allpattern()) {
  63. 			throw CombinationGeneratorException();
  64. 		}
  65. 		while (_c != idx) {
  66. 			next();
  67. 		}
  68. 		return _list;
  69. 	}
  70.  
  71. 	const int* next() {
  72. 		if (_i > _size) {
  73. 			_list[_j] = 0;
  74. 			_j++;
  75. 			_i--;
  76. 		}
  77. 		for (;;) {
  78. 			while (_j == _size) {
  79. 				_i--;
  80. 				if (_i < 1) {
  81. 					_i = 1;
  82. 					_j = 0;
  83. 					_p = 0;
  84. 					_c = 0;
  85. 				} else {
  86. 					_p--;
  87. 					_j = _stack[_p];
  88. 					_list[_j] = 0;
  89. 					_j++;
  90. 				}
  91. 			}
  92. 			if (_list[_j] == 0) {
  93. 				_list[_j] = _i;
  94. 				_i++;
  95. 				if (_i > _size) {
  96. 					_c++;
  97. 					break;
  98. 				} else {
  99. 					_stack[_p] = _j;
  100. 					_p++;
  101. 					_j = 0;
  102. 				}
  103. 			} else {
  104. 				_j++;
  105. 			}
  106. 		}
  107. 		return _list;
  108. 	}
  109.  
  110. 	int length() const {
  111. 		return _size;
  112. 	}
  113.  
  114. 	int allpattern() {
  115. 		if (_all == 0) {
  116. 			_all = 1;
  117. 			for (int i = 2; i <= _size; i++) {
  118. 				_all *= i;
  119. 			}
  120. 		}
  121. 		return _all;
  122. 	}
  123. };
  124.  
  125.  
  126. int main() {
  127.  
  128. 	try {
  129. 		CombinationGenerator gen(15); 
  130.  
  131. 		cout << "length: " << gen.length() << endl; 
  132. 		cout << "all pattern: " << gen.allpattern() << endl;
  133.  
  134. 		int idx = 36690094;
  135.  
  136. 		cout << setfill('.') << setw(10) << idx << ": ";
  137. 		for (int i = 0; i < gen.length(); i++) {
  138. 			cout << "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[gen.get(idx)[i]];
  139. 		}
  140. 		cout << endl;
  141.  
  142. 	} catch (CombinationGeneratorException& ex) {
  143. 		cout << "error" << endl;
  144. 	}
  145.  
  146. 	return 0;
  147. }
Success #stdin #stdout 4.25s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
length: 15
all pattern: 2004310016
..36690094: ABCDGFOMJNKILHE
https://ideone.com/8Ifvzn
language:
C++ (gcc 8.3)
created:
10 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!