fork(1) download 
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.  
  5. class PatternGeneratorException {};
  6.  
  7. class PatternGenerator
  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. 	int _all;
  18.  
  19. 	PatternGenerator() {}
  20.  
  21. 	PatternGenerator(int srcsize, int len, int a) 
  22. 				: _srcsize(srcsize), _len(len), _all(a) {
  23.  
  24. 		if (_srcsize < 2 || _len < 2 || _srcsize < _len) {
  25. 			throw PatternGeneratorException();
  26. 		}		
  27. 		_src = new int[_srcsize];
  28. 		_flag = new int[_srcsize];
  29.  
  30. 		_list = new int[_len];
  31. 		_indexes = new int[len];
  32.  
  33. 		for (int i = 0; i < _srcsize; i++) {
  34. 			_flag[i] = 0;
  35. 		}		
  36. 	}
  37. public:
  38.  
  39. 	static int nCr(int n, int r);
  40. 	static int nPr(int n, int r);
  41.  
  42. 	PatternGenerator(int srcsize, int len) 
  43. 			: PatternGenerator(srcsize, len, 0) {
  44.  
  45. 		for (int i = 0; i < _srcsize; i++) {
  46. 			_src[i] = i + 1;
  47. 		}		
  48.  
  49. 		reset();
  50. 	}
  51.  
  52. 	PatternGenerator(int size) 
  53. 			: PatternGenerator(size, size) {
  54. 	}
  55.  
  56. 	PatternGenerator(const int *sortedsrc, int srcsize, int len)
  57. 			: PatternGenerator(srcsize, len, 0) {
  58.  
  59. 		memcpy(_src, sortedsrc, sizeof(int) * _srcsize);
  60.  
  61. 		reset();
  62. 	}
  63.  
  64. 	~PatternGenerator() {
  65. 		delete [] _src;
  66. 		delete [] _flag;
  67. 		delete [] _list;
  68. 		delete [] _indexes;
  69. 	}
  70.  
  71. 	int length()     const { return _len; }
  72. 	int sourcesize() const { return _srcsize; }
  73. 	int count()      const { return _count; }
  74. 	const int* source() const { return _src; }
  75.  
  76. 	void reset() {
  77. 		for (int i = 0; i < _len; i++) {
  78. 			_flag[_indexes[i]] = 0;
  79. 		}
  80. 		for (int i = 0; i < _len; i++) {
  81. 			_indexes[i] = i;
  82. 			_list[i] = _src[_indexes[i]];
  83. 			_flag[_indexes[i]] = 1;
  84. 		}
  85. 		_count = 0;
  86. 	}
  87.  
  88. 	int allpattern() {
  89. 		if (_all == 0) {
  90. 			_all = nCr(_srcsize, _len) * nPr(_len, _len);
  91. 			int c = 0, r = 0;
  92. 			for (int i = 1; i < _srcsize; i++) {
  93. 				if (_src[i - 1] == _src[i]) {
  94. 					c++;
  95. 					r++;
  96. 				} else {
  97. 					if (c > 0) {
  98. 						c++;
  99. 						_all /= nPr(c, c);
  100. 						c = 0;
  101. 					}
  102. 				}
  103. 			}
  104. 			if (c > 0) {
  105. 				c++;
  106. 				_all /= nPr(c, c);
  107. 			}
  108. 			if (r > 0 && _len < _srcsize) {
  109. 				// 計算方法不明
  110. 				_all =  nCr(_srcsize, _len) * nPr(_len, _len);
  111. 			}
  112. 		}
  113. 		return _all;
  114. 	}
  115.  
  116. 	const int* get(int n) {
  117. 		if (n < 1 || n > allpattern()) {
  118. 			throw PatternGeneratorException();
  119. 		}
  120. 		if (n < _count) {
  121. 			reset();
  122. 		}
  123. 		while (n != _count) {
  124. 			next();
  125. 		}
  126. 		return _list;
  127. 	}
  128.  
  129. 	int hasNext() {
  130. 		if (_count == 0) {
  131. 			return 1;
  132. 		}
  133. 		for (int i = 0; i < _len; i++) {
  134. 			if (_src[_indexes[i]] != _src[_srcsize - i - 1]) {
  135. 				return 1;
  136. 			}
  137. 		}
  138. 		return 0;
  139. 	}
  140.  
  141. 	const int* next() {
  142.  
  143. 		if (_count == 0) {
  144. 			_count++;
  145. 			return _list;
  146. 		}
  147.  
  148. 		int i, j, b, f;
  149.  
  150. 		i = _len - 1;
  151. 		_flag[_indexes[i]] = 0;
  152.  
  153. 		f = 1;
  154.  
  155. 		for (;;) {
  156. 			if (f) {
  157. 				b = _src[_indexes[i]];
  158. 				for (j = _indexes[i] + 1; j < _srcsize; j++) {
  159. 					if (_flag[j] == 0 && _src[j] != b) {
  160. 						break;
  161. 					}
  162. 				}
  163. 			} else {
  164. 				for (j = 0; j < _srcsize; j++) {
  165. 					if (_flag[j] == 0) {
  166. 						break;
  167. 					}
  168. 				}
  169. 				f = 1;
  170. 			}
  171. 			if (j == _srcsize) {
  172. 				i--;
  173. 				if (i < 0) {
  174. 					reset();
  175. 					break;
  176. 				} else {
  177. 					_flag[_indexes[i]] = 0;
  178. 				}
  179. 			} else {
  180. 				_indexes[i] = j;
  181. 				_list[i] = _src[_indexes[i]];
  182. 				_flag[_indexes[i]] = 1;
  183. 				i++;
  184. 				if (i == _len) {
  185. 					// kakutei
  186. 					break;
  187. 				} else {
  188. 					f = 0;
  189. 				}
  190. 			}
  191. 		}
  192. 		_count++;
  193. 		return _list;
  194. 	}
  195. };
  196.  
  197. int PatternGenerator::nCr(int n, int r) {
  198. 	if (n < 0 || r < 0 || n < r) {
  199. 		return 0;
  200. 	}
  201. 	if (n - r < r) {
  202. 		r = n - r;
  203. 	}
  204. 	int c = 1;
  205. 	for (int i = 1; i <= r; i++) {
  206. 		c *= n;
  207. 		c /= i;
  208. 		n--;
  209. 	}
  210. 	return c;
  211. }
  212.  
  213. int PatternGenerator::nPr(int n, int r) {
  214. 	if (n < 0 || r < 0 || n < r) {
  215. 		return 0;
  216. 	}
  217. 	int p = 1;
  218. 	while (r > 0) {
  219. 		p *= n;
  220. 		n--;
  221. 		r--;
  222. 	}
  223. 	return p;
  224. }
  225.  
  226. int main() {
  227. 	int src[] = { 1, 2, 2, 2, 5, 7, 7, 9};
  228. 	int len = sizeof(src) / sizeof(src[0]);
  229. 	PatternGenerator gen(15);
  230. 	PatternGenerator gen2(src, len, 3);
  231.  
  232. 	cout << "all pattern: " << gen.allpattern() << endl;
  233.  
  234. 	const int *kk = gen.get(1500);
  235. 	cout.fill('.');
  236. 	cout.width(8);
  237. 	cout << gen.count() << ": ";
  238. 	for (int i = 0; i < gen.length(); i++) {
  239. 		cout << "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[kk[i]];
  240. 	}
  241. 	cout << endl << endl;
  242.  
  243. 	kk = gen.get(150);
  244. 	cout.fill('.');
  245. 	cout.width(8);
  246. 	cout << gen.count() << ": ";
  247. 	for (int i = 0; i < gen.length(); i++) {
  248. 		cout << "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[kk[i]];
  249. 	}
  250. 	cout << endl << endl;
  251.  
  252. 	// 正しく計算されない！
  253. 	cout << "all pattern 2: " << gen2.allpattern() << endl;
  254.  
  255. 	while (gen2.hasNext()) {
  256. 		kk = gen2.next();
  257. 		cout.fill('.');
  258. 		cout.width(8);
  259. 		cout << gen2.count() << ": ";
  260. 		for (int i = 0; i < gen2.length(); i++) {
  261. 			cout << "0123456789"[kk[i]];
  262. 		}
  263. 		cout << endl;
  264. 	}
  265.  
  266.  
  267.  
  268. 	return 0;
  269. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin 
Standard input is empty
stdout 
all pattern: 2004310016
....1500: ABCDEFGHKIMLONJ

.....150: ABCDEFGHIKLJONM

all pattern 2: 336
.......1: 122
.......2: 125
.......3: 127
.......4: 129
.......5: 152
.......6: 157
.......7: 159
.......8: 172
.......9: 175
......10: 177
......11: 179
......12: 192
......13: 195
......14: 197
......15: 212
......16: 215
......17: 217
......18: 219
......19: 221
......20: 222
......21: 225
......22: 227
......23: 229
......24: 251
......25: 252
......26: 257
......27: 259
......28: 271
......29: 272
......30: 275
......31: 277
......32: 279
......33: 291
......34: 292
......35: 295
......36: 297
......37: 512
......38: 517
......39: 519
......40: 521
......41: 522
......42: 527
......43: 529
......44: 571
......45: 572
......46: 577
......47: 579
......48: 591
......49: 592
......50: 597
......51: 712
......52: 715
......53: 717
......54: 719
......55: 721
......56: 722
......57: 725
......58: 727
......59: 729
......60: 751
......61: 752
......62: 757
......63: 759
......64: 771
......65: 772
......66: 775
......67: 779
......68: 791
......69: 792
......70: 795
......71: 797
......72: 912
......73: 915
......74: 917
......75: 921
......76: 922
......77: 925
......78: 927
......79: 951
......80: 952
......81: 957
......82: 971
......83: 972
......84: 975
......85: 977
https://ideone.com/hsSjW8
language:
C++ (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!