fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. typedef struct _PatternGenParams
  6. {
  7. 	int *src;
  8. 	int *flag;
  9. 	int *list;
  10. 	int *indexes;
  11. 	int srcsize;
  12. 	int len;
  13. 	int count;
  14. 	int all;
  15. } PatternGenParams;
  16.  
  17. extern int PatternGenInitP(PatternGenParams *params, int srcsize, int len);
  18. extern int PatternGenInitA(PatternGenParams *params, int size);
  19. extern int PatternGenInitBySrc(PatternGenParams *params, const int *sortedsrc ,int srcsize, int len);
  20. extern void PatternGenReset(PatternGenParams *params);
  21. extern void PatternGenRelease(PatternGenParams *params);
  22. extern int PatternGenAllPattern(PatternGenParams *params);
  23. extern int PatternGenHasNext(PatternGenParams *params);
  24. extern int PatternGenCount(PatternGenParams *params);
  25. extern int PatternGenLength(PatternGenParams *params);
  26. extern const int* PatternGenGet(PatternGenParams *params, int n);
  27. extern const int* PatternGenNext(PatternGenParams *params);
  28.  
  29. static int PatternGenCheckParams(PatternGenParams *params);
  30. static int PatternGenInitCommon(PatternGenParams *params, int srcsize, int len);
  31. static int nCr(int n, int r);
  32. static int nPr(int n, int r);
  33.  
  34. static int PatternGenCheckParams(PatternGenParams *params) {
  35. 	return params == NULL
  36. 		|| params->src == NULL
  37. 		|| params->flag == NULL
  38. 		|| params->list == NULL
  39. 		|| params->indexes == NULL
  40. 		|| params->count < 0
  41. 		|| params->all < 0;
  42. }
  43.  
  44. static int PatternGenInitCommon(PatternGenParams *params, int srcsize, int len) {
  45. 	if (srcsize < 2 || len < 2 || srcsize < len || params == NULL) {
  46. 		return 1;
  47. 	}
  48.  
  49. 	params->srcsize = srcsize;
  50. 	params->len = len;
  51. 	params->count = 0;
  52. 	params->all = 0;
  53.  
  54. 	params->src = (int*)calloc(params->srcsize, sizeof(int));
  55. 	params->flag = (int*)calloc(params->srcsize, sizeof(int));
  56.  
  57. 	params->indexes = (int*)calloc(params->len, sizeof(int));
  58. 	params->list = (int*)calloc(params->len, sizeof(int));
  59.  
  60. 	return 0;
  61. }
  62.  
  63. extern int PatternGenInitP(PatternGenParams *params, int srcsize, int len) {
  64. 	int i;
  65. 	if (PatternGenInitCommon(params, srcsize, len)) {
  66. 		return 1;
  67. 	}
  68. 	for (i = 0; i < params->srcsize; i++) {
  69. 		params->src[i] = i + 1;
  70. 	}
  71. 	PatternGenReset(params);
  72. 	return 0;
  73. }
  74.  
  75. extern int PatternGenInitA(PatternGenParams *params, int size) {
  76. 	return PatternGenInitP(params, size, size);
  77. }
  78.  
  79. extern int PatternGenInitBySrc(PatternGenParams *params, const int *sortedsrc ,int srcsize, int len) {
  80. 	if (PatternGenInitCommon(params, srcsize, len)) {
  81. 		return 1;
  82. 	}
  83. 	memcpy(params->src, sortedsrc, sizeof(int) * params->srcsize);
  84.  
  85. 	PatternGenReset(params);
  86. 	return 0;
  87. }
  88.  
  89. extern void PatternGenRelease(PatternGenParams *params) {
  90. 	if (params == NULL) {
  91. 		return;
  92. 	}
  93. 	if (params->src) {
  94. 		free(params->src);
  95. 		params->src = NULL;
  96. 	}
  97. 	if (params->flag) {
  98. 		free(params->flag);
  99. 		params->flag = NULL;
  100. 	}
  101. 	if (params->list) {
  102. 		free(params->list);
  103. 		params->list = NULL;
  104. 	}
  105. 	if (params->indexes) {
  106. 		free(params->indexes);
  107. 		params->indexes = NULL;
  108. 	}
  109. 	params->count = params->all = 0;
  110. }
  111.  
  112. extern void PatternGenReset(PatternGenParams *params) {
  113. 	int i;
  114. 	if (PatternGenCheckParams(params)) {
  115. 		return;
  116. 	}
  117. 	for (i = 0; i < params->len; i++) {
  118. 		params->flag[params->indexes[i]] = 0;
  119. 	}
  120. 	for (i = 0; i < params->len; i++) {
  121. 		params->indexes[i] = i;
  122. 		params->list[i] = params->src[params->indexes[i]];
  123. 		params->flag[params->indexes[i]] = 1;
  124. 	}
  125. 	params->count = 0;
  126. }
  127.  
  128. extern int PatternGenAllPattern(PatternGenParams *params) {
  129. 	int i, c;
  130. 	if (params->all == 0) {
  131. 		params->all = nCr(params->srcsize, params->len) 
  132. 			        * nPr(params->len, params->len);
  133. 		c = 0;
  134. 		for (i = 1; i < params->srcsize; i++) {
  135. 			if (params->src[i - 1] == params->src[i]) {
  136. 				c++;
  137. 			} else {
  138. 				if (c) {
  139. 					c++;
  140. 					params->all /= nPr(c, c);
  141. 					c = 0;
  142. 				}
  143. 			}
  144. 		}
  145. 		if (c) {
  146. 			params->all /= nPr(c, c);
  147. 		}
  148. 	}
  149. 	return params->all;
  150. }
  151.  
  152. extern const int* PatternGenGet(PatternGenParams *params, int n) {
  153. 	if (PatternGenCheckParams(params)) {
  154. 		return NULL;
  155. 	}
  156. 	if (n < 1 || n > PatternGenAllPattern(params)) {
  157. 		return NULL;
  158. 	}
  159. 	while (n != params->count) {
  160. 		PatternGenNext(params);
  161. 	}
  162. 	return params->list;
  163. }
  164.  
  165. extern int PatternGenHasNext(PatternGenParams *params) {
  166. 	int i;
  167. 	if (PatternGenCheckParams(params)) {
  168. 		return 0;
  169. 	}
  170. 	if (params->count == 0) {
  171. 		return 1;
  172. 	}
  173. 	for (i = 0; i < params->len; i++) {
  174. 		if (params->src[params->indexes[i]] 
  175. 				!= params->src[params->srcsize - i - 1]) {
  176. 			return 1;
  177. 		}
  178. 	}
  179. 	return 0;
  180. }
  181.  
  182. const int* PatternGenNext(PatternGenParams *params) {
  183. 	int i, j, b, f;
  184.  
  185. 	if (PatternGenCheckParams(params)) {
  186. 	 return NULL;
  187. 	}
  188.  
  189. 	if (params->count == 0) {
  190. 		params->count++;
  191. 		return params->list;
  192. 	}
  193.  
  194. 	i = params->len - 1;
  195. 	params->flag[params->indexes[i]] = 0;
  196.  
  197. 	f = 1;
  198.  
  199. 	for (;;) {
  200. 		if (f) {
  201. 			b = params->src[params->indexes[i]];
  202. 			for (j = params->indexes[i] + 1; j < params->srcsize; j++) {
  203. 				if (params->flag[j] == 0 && params->src[j] != b) {
  204. 					break;
  205. 				}
  206. 			}
  207. 		} else {
  208. 			for (j = 0; j < params->srcsize; j++) {
  209. 				if (params->flag[j] == 0) {
  210. 					break;
  211. 				}
  212. 			}
  213. 			f = 1;
  214. 		}
  215. 		if (j == params->srcsize) {
  216. 			i--;
  217. 			if (i < 0) {
  218. 				PatternGenReset(params);
  219. 				break;
  220. 			} else {
  221. 				params->flag[params->indexes[i]] = 0;
  222. 			}
  223. 		} else {
  224. 			params->indexes[i] = j;
  225. 			params->list[i] = params->src[params->indexes[i]];
  226. 			params->flag[params->indexes[i]] = 1;
  227. 			i++;
  228. 			if (i == params->len) {
  229. 				// kakutei
  230. 				break;
  231. 			} else {
  232. 				f = 0;
  233. 			}
  234. 		}
  235. 	}
  236. 	params->count++;
  237. 	return params->list;
  238. }
  239.  
  240. extern int PatternGenCount(PatternGenParams *params) {
  241. 	if (PatternGenCheckParams(params)) {
  242. 		return 0;
  243. 	}
  244. 	return params->count;
  245. }
  246.  
  247. extern int PatternGenLength(PatternGenParams *params) {
  248. 	if (PatternGenCheckParams(params)) {
  249. 		return 0;
  250. 	}
  251. 	return params->len;
  252. }
  253.  
  254. static int nCr(int n, int r) {
  255. 	int i, c;
  256. 	if (n < 0 || r < 0 || n < r) {
  257. 		return 0;
  258. 	}
  259. 	if (n - r < r) {
  260. 		r = n - r;
  261. 	}
  262. 	c = 1;
  263. 	for (i = 1; i <= r; i++) {
  264. 		c *= n;
  265. 		c /= i;
  266. 		n--;
  267. 	}
  268. 	return c;
  269. }
  270.  
  271. static int nPr(int n, int r) {
  272. 	int p;
  273. 	if (n < 0 || r < 0 || n < r) {
  274. 		return 0;
  275. 	}
  276. 	p = 1;
  277. 	while (r > 0) {
  278. 		p *= n;
  279. 		n--;
  280. 		r--;
  281. 	}
  282. 	return p;
  283. }
  284.  
  285.  
  286. int main(void) {
  287.  
  288. 	PatternGenParams params, params2, params3;
  289. 	PatternGenParams *gen = &params;
  290. 	PatternGenParams *gen2 = &params2;
  291. 	PatternGenParams *gen3 = &params3;
  292. 	const int *k;
  293. 	int i;
  294. 	int src[] = { 1, 2, 2, 5};
  295. 	int len = sizeof(src) / sizeof(src[0]);
  296.  
  297. 	PatternGenInitA(gen, 4);
  298. 	PatternGenInitP(gen2, 5, 3);
  299. 	PatternGenInitBySrc(gen3, src, len, len);
  300.  
  301. 	k = PatternGenGet(gen, 15);
  302. 	printf("%08d: ", PatternGenCount(gen));
  303. 	for (i = 0; i < PatternGenLength(gen); i++) {
  304. 		putchar("_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[k[i]]);
  305. 	} 
  306. 	putchar('\n');	
  307.  
  308. 	printf("\n");
  309.  
  310. 	PatternGenReset(gen);
  311.  
  312. 	printf("all pattern: %d\n", PatternGenAllPattern(gen));
  313.  
  314. 	while (PatternGenHasNext(gen)) {
  315. 		k = PatternGenNext(gen);
  316. 		printf("%08d: ", PatternGenCount(gen));
  317. 		for (i = 0; i < PatternGenLength(gen); i++) {
  318. 			putchar("_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[k[i]]);
  319. 		} 
  320. 		putchar('\n');
  321. 	}
  322.  
  323. 	printf("\n\n");
  324.  
  325. 	printf("all pattern 2: %d\n", PatternGenAllPattern(gen2));
  326.  
  327. 	while (PatternGenHasNext(gen2)) {
  328. 		k = PatternGenNext(gen2);
  329. 		printf("%08d: ", PatternGenCount(gen2));
  330. 		for (i = 0; i < PatternGenLength(gen2); i++) {
  331. 			putchar("_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[k[i]]);
  332. 		} 
  333. 		putchar('\n');
  334. 	}
  335.  
  336. 	printf("\n\n");
  337.  
  338. 	printf("all pattern 3: %d\n", PatternGenAllPattern(gen3));
  339.  
  340. 	while (PatternGenHasNext(gen3)) {
  341. 		k = PatternGenNext(gen3);
  342. 		printf("%08d: ", PatternGenCount(gen3));
  343. 		for (i = 0; i < PatternGenLength(gen3); i++) {
  344. 			putchar("0123456789"[k[i]]);
  345. 		} 
  346. 		putchar('\n');
  347. 	}
  348.  
  349. 	PatternGenRelease(gen);
  350. 	PatternGenRelease(gen2);
  351. 	PatternGenRelease(gen3);
  352.  
  353. 	return 0;
  354. }
  355.  
Success #stdin #stdout 0s 2432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
00000015: CBAD

all pattern: 24
00000001: ABCD
00000002: ABDC
00000003: ACBD
00000004: ACDB
00000005: ADBC
00000006: ADCB
00000007: BACD
00000008: BADC
00000009: BCAD
00000010: BCDA
00000011: BDAC
00000012: BDCA
00000013: CABD
00000014: CADB
00000015: CBAD
00000016: CBDA
00000017: CDAB
00000018: CDBA
00000019: DABC
00000020: DACB
00000021: DBAC
00000022: DBCA
00000023: DCAB
00000024: DCBA


all pattern 2: 60
00000001: ABC
00000002: ABD
00000003: ABE
00000004: ACB
00000005: ACD
00000006: ACE
00000007: ADB
00000008: ADC
00000009: ADE
00000010: AEB
00000011: AEC
00000012: AED
00000013: BAC
00000014: BAD
00000015: BAE
00000016: BCA
00000017: BCD
00000018: BCE
00000019: BDA
00000020: BDC
00000021: BDE
00000022: BEA
00000023: BEC
00000024: BED
00000025: CAB
00000026: CAD
00000027: CAE
00000028: CBA
00000029: CBD
00000030: CBE
00000031: CDA
00000032: CDB
00000033: CDE
00000034: CEA
00000035: CEB
00000036: CED
00000037: DAB
00000038: DAC
00000039: DAE
00000040: DBA
00000041: DBC
00000042: DBE
00000043: DCA
00000044: DCB
00000045: DCE
00000046: DEA
00000047: DEB
00000048: DEC
00000049: EAB
00000050: EAC
00000051: EAD
00000052: EBA
00000053: EBC
00000054: EBD
00000055: ECA
00000056: ECB
00000057: ECD
00000058: EDA
00000059: EDB
00000060: EDC


all pattern 3: 12
00000001: 1225
00000002: 1252
00000003: 1522
00000004: 2125
00000005: 2152
00000006: 2215
00000007: 2251
00000008: 2512
00000009: 2521
00000010: 5122
00000011: 5212
00000012: 5221
https://ideone.com/93WLZ6
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!