fork(1) download 
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. class PatternGenerator2Exception {};
  6.  
  7. class PatternGenerator2
  8. {
  9. private:
  10. 	int *_src;
  11. 	int *_flag;
  12. 	int *_indexes;
  13. 	int *_list;
  14. 	int _srcsize;
  15. 	int _len;
  16. 	int _count;
  17. 	PatternGenerator2(int srcsize, int len, int c) 
  18. 				: _srcsize(srcsize), _len(len), _count(c) {
  19.  
  20. 		if (_srcsize < 2 || _len < 2 || _srcsize < _len) {
  21. 			throw PatternGenerator2Exception();
  22. 		}		
  23. 		_src = new int[_srcsize];
  24. 		_flag = new int[_srcsize];
  25.  
  26. 		_list = new int[_len];
  27. 		_indexes = new int[len];
  28.  
  29. 		for (int i = 0; i < _srcsize; i++) {
  30. 			_flag[i] = 0;
  31. 		}		
  32. 	}
  33. public:
  34.  
  35. 	PatternGenerator2(int srcsize, int len) 
  36. 			: PatternGenerator2(srcsize, len, 0) {
  37.  
  38. 		for (int i = 0; i < _srcsize; i++) {
  39. 			_src[i] = i + 1;
  40. 		}		
  41.  
  42. 		reset();
  43. 	}
  44.  
  45. 	PatternGenerator2(int size) 
  46. 			: PatternGenerator2(size, size) {
  47. 	}
  48.  
  49. 	PatternGenerator2(const int *sortedsrc, int srcsize, int len)
  50. 			: PatternGenerator2(srcsize, len, 0) {
  51.  
  52. 		memcpy(_src, sortedsrc, sizeof(int) * _srcsize);
  53.  
  54. 		reset();
  55. 	}
  56.  
  57. 	~PatternGenerator2() {
  58. 		delete [] _src;
  59. 		delete [] _flag;
  60. 		delete [] _list;
  61. 		delete [] _indexes;
  62. 	}
  63.  
  64. 	int length()     const { return _len; }
  65. 	int sourcesize() const { return _srcsize; }
  66. 	int count()      const { return _count; }
  67.  
  68. 	void reset() {
  69. 		for (int i = 0; i < _len; i++) {
  70. 			_flag[_indexes[i]] = 0;
  71. 		}
  72. 		for (int i = 0; i < _len; i++) {
  73. 			_indexes[i] = i;
  74. 			_list[i] = _src[_indexes[i]];
  75. 			_flag[_indexes[i]] = 1;
  76. 		}
  77. 		_count = 0;
  78. 	}
  79.  
  80. 	int hasNext() {
  81. 		if (_count == 0) {
  82. 			return 1;
  83. 		}
  84. 		for (int i = 0; i < _len; i++) {
  85. 			if (_src[_indexes[i]] != _src[_srcsize - i - 1]) {
  86. 				return 1;
  87. 			}
  88. 		}
  89. 		return 0;
  90. 	}
  91.  
  92. 	const int* next() {
  93.  
  94. 		if (_count == 0) {
  95. 			_count++;
  96. 			return _list;
  97. 		}
  98.  
  99. 		int i, j, b, f;
  100.  
  101. 		i = _len - 1;
  102. 		_flag[_indexes[i]] = 0;
  103.  
  104. 		f = 1;
  105.  
  106. 		for (;;) {
  107. 			if (f) {
  108. 				b = _src[_indexes[i]];
  109. 				for (j = _indexes[i] + 1; j < _srcsize; j++) {
  110. 					if (_flag[j] == 0 && _src[j] != b) {
  111. 						break;
  112. 					}
  113. 				}
  114. 			} else {
  115. 				for (j = 0; j < _srcsize; j++) {
  116. 					if (_flag[j] == 0) {
  117. 						break;
  118. 					}
  119. 				}
  120. 				f = 1;
  121. 			}
  122. 			if (j == _srcsize) {
  123. 				i--;
  124. 				if (i < 0) {
  125. 					reset();
  126. 					break;
  127. 				} else {
  128. 					_flag[_indexes[i]] = 0;
  129. 				}
  130. 			} else {
  131. 				_indexes[i] = j;
  132. 				_list[i] = _src[_indexes[i]];
  133. 				_flag[_indexes[i]] = 1;
  134. 				i++;
  135. 				if (i == _len) {
  136. 					// kakutei
  137. 					break;
  138. 				} else {
  139. 					f = 0;
  140. 				}
  141. 			}
  142. 		}
  143. 		_count++;
  144. 		return _list;
  145. 	}
  146. };
  147.  
  148. int nCr(int n, int r) {
  149. 	if (n < 0 || r < 0 || n < r) {
  150. 		return 0;
  151. 	}
  152. 	if (n - r < r) {
  153. 		r = n - r;
  154. 	}
  155. 	int c = 1;
  156. 	for (int i = 1; i <= r; i++) {
  157. 		c *= n;
  158. 		c /= i;
  159. 		n--;
  160. 	}
  161. 	return c;
  162. }
  163.  
  164. int nPr(int n, int r) {
  165. 	if (n < 0 || r < 0 || n < r) {
  166. 		return 0;
  167. 	}
  168. 	int p = 1;
  169. 	while (r > 0) {
  170. 		p *= n;
  171. 		n--;
  172. 		r--;
  173. 	}
  174. 	return p;
  175. }
  176.  
  177. int main() {
  178.  
  179. 	PatternGenerator2 gen(15);
  180.  
  181. 	for (;;) {
  182. 		const int *k = gen.next();
  183. 		if (gen.count() == 36690094) {
  184. 			cout << gen.count() << ": ";
  185. 			for (int i = 0; i < gen.length(); i++) {
  186. 				cout << "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[k[i]];
  187. 			}
  188. 			cout << endl;
  189. 			break;
  190. 		}
  191. 	}
  192.  
  193. 	return 0;
  194. }
Success #stdin #stdout 3.79s 3428KB
comments (?)
stdin 
Standard input is empty
stdout 
36690094: ABCDOFENLIKMHJG
https://ideone.com/DSyREF
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!