fork(1) 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(4); 
  130.  
  131. 		cout << "all pattern: " << gen.allpattern() << endl;
  132.  
  133. 		for (int j = 0; j <= gen.allpattern(); j++) {
  134.  
  135. 			cout << setfill(' ') << setw(4) << (j + 1) << ": ";
  136.  
  137. 			const int *k = gen.next();
  138.  
  139. 			for (int i = 0; i < gen.length(); i++) {
  140. 				cout << "_ABCDEFG"[k[i]];
  141. 			}
  142.  
  143. 			cout << endl;
  144. 		}
  145.  
  146. 		cout << endl;
  147.  
  148. 		gen.reset();
  149. 		while (gen.hasNext()) {
  150. 			const int *k = gen.next();
  151. 			for (int i = 0; i < gen.length(); i++) {
  152. 				cout << "_ABCDEFG"[k[i]];
  153. 			}
  154. 			cout << endl;
  155. 		}
  156.  
  157. 		cout << endl;
  158.  
  159. 		cout << setfill('0') << setw(4) << 18 << ": ";
  160. 		for (int i = 0; i < gen.length(); i++) {
  161. 			cout << "_ABCDEFG"[gen.get(18)[i]];
  162. 		}
  163. 		cout << endl;
  164.  
  165. 	} catch (CombinationGeneratorException& ex) {
  166. 		cout << "error" << endl;
  167. 	}
  168.  
  169. 	return 0;
  170. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
all pattern: 24
   1: ABCD
   2: ABDC
   3: ACBD
   4: ADBC
   5: ACDB
   6: ADCB
   7: BACD
   8: BADC
   9: CABD
  10: DABC
  11: CADB
  12: DACB
  13: BCAD
  14: BDAC
  15: CBAD
  16: DBAC
  17: CDAB
  18: DCAB
  19: BCDA
  20: BDCA
  21: CBDA
  22: DBCA
  23: CDBA
  24: DCBA
  25: ABCD

ABCD
ABDC
ACBD
ADBC
ACDB
ADCB
BACD
BADC
CABD
DABC
CADB
DACB
BCAD
BDAC
CBAD
DBAC
CDAB
DCAB
BCDA
BDCA
CBDA
DBCA
CDBA
DCBA

0018: DCAB
https://ideone.com/OLUrjj
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!