fork download 
  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;
  289. 	PatternGenParams *gen = &params;
  290. 	const int *k;
  291. 	int i;
  292.  
  293. 	PatternGenInitA(gen, 15);
  294.  
  295. 	k = PatternGenGet(gen, 36690094);
  296. 	printf("%08d: ", PatternGenCount(gen));
  297. 	for (i = 0; i < PatternGenLength(gen); i++) {
  298. 		putchar("_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[k[i]]);
  299. 	} 
  300. 	putchar('\n');	
  301.  
  302. 	PatternGenRelease(gen);
  303.  
  304. 	return 0;
  305. }
  306.  
Success #stdin #stdout 4.1s 2432KB
comments (?)
stdin 
Standard input is empty
stdout 
36690094: ABCDOFENLIKMHJG
https://ideone.com/mv1Cjb
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!