#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _PatternGenParams
{
	int *src;
	int *flag;
	int *list;
	int *indexes;
	int srcsize;
	int len;
	int count;
	int all;
} PatternGenParams;

extern int PatternGenInitP(PatternGenParams *params, int srcsize, int len);
extern int PatternGenInitA(PatternGenParams *params, int size);
extern int PatternGenInitBySrc(PatternGenParams *params, const int *sortedsrc ,int srcsize, int len);
extern void PatternGenReset(PatternGenParams *params);
extern void PatternGenRelease(PatternGenParams *params);
extern int PatternGenAllPattern(PatternGenParams *params);
extern int PatternGenHasNext(PatternGenParams *params);
extern int PatternGenCount(PatternGenParams *params);
extern int PatternGenLength(PatternGenParams *params);
extern const int* PatternGenGet(PatternGenParams *params, int n);
extern const int* PatternGenNext(PatternGenParams *params);

static int PatternGenCheckParams(PatternGenParams *params);
static int PatternGenInitCommon(PatternGenParams *params, int srcsize, int len);
static int nCr(int n, int r);
static int nPr(int n, int r);

static int PatternGenCheckParams(PatternGenParams *params) {
	return params == NULL
		|| params->src == NULL
		|| params->flag == NULL
		|| params->list == NULL
		|| params->indexes == NULL
		|| params->count < 0
		|| params->all < 0;
}

static int PatternGenInitCommon(PatternGenParams *params, int srcsize, int len) {
	if (srcsize < 2 || len < 2 || srcsize < len || params == NULL) {
		return 1;
	}
	
	params->srcsize = srcsize;
	params->len = len;
	params->count = 0;
	params->all = 0;
	
	params->src = (int*)calloc(params->srcsize, sizeof(int));
	params->flag = (int*)calloc(params->srcsize, sizeof(int));
	
	params->indexes = (int*)calloc(params->len, sizeof(int));
	params->list = (int*)calloc(params->len, sizeof(int));
	
	return 0;
}

extern int PatternGenInitP(PatternGenParams *params, int srcsize, int len) {
	int i;
	if (PatternGenInitCommon(params, srcsize, len)) {
		return 1;
	}
	for (i = 0; i < params->srcsize; i++) {
		params->src[i] = i + 1;
	}
	PatternGenReset(params);
	return 0;
}

extern int PatternGenInitA(PatternGenParams *params, int size) {
	return PatternGenInitP(params, size, size);
}

extern int PatternGenInitBySrc(PatternGenParams *params, const int *sortedsrc ,int srcsize, int len) {
	if (PatternGenInitCommon(params, srcsize, len)) {
		return 1;
	}
	memcpy(params->src, sortedsrc, sizeof(int) * params->srcsize);
	
	PatternGenReset(params);
	return 0;
}

extern void PatternGenRelease(PatternGenParams *params) {
	if (params == NULL) {
		return;
	}
	if (params->src) {
		free(params->src);
		params->src = NULL;
	}
	if (params->flag) {
		free(params->flag);
		params->flag = NULL;
	}
	if (params->list) {
		free(params->list);
		params->list = NULL;
	}
	if (params->indexes) {
		free(params->indexes);
		params->indexes = NULL;
	}
	params->count = params->all = 0;
}

extern void PatternGenReset(PatternGenParams *params) {
	int i;
	if (PatternGenCheckParams(params)) {
		return;
	}
	for (i = 0; i < params->len; i++) {
		params->flag[params->indexes[i]] = 0;
	}
	for (i = 0; i < params->len; i++) {
		params->indexes[i] = i;
		params->list[i] = params->src[params->indexes[i]];
		params->flag[params->indexes[i]] = 1;
	}
	params->count = 0;
}

extern int PatternGenAllPattern(PatternGenParams *params) {
	int i, c;
	if (params->all == 0) {
		params->all = nCr(params->srcsize, params->len) 
			        * nPr(params->len, params->len);
		c = 0;
		for (i = 1; i < params->srcsize; i++) {
			if (params->src[i - 1] == params->src[i]) {
				c++;
			} else {
				if (c) {
					c++;
					params->all /= nPr(c, c);
					c = 0;
				}
			}
		}
		if (c) {
			params->all /= nPr(c, c);
		}
	}
	return params->all;
}

extern const int* PatternGenGet(PatternGenParams *params, int n) {
	if (PatternGenCheckParams(params)) {
		return NULL;
	}
	if (n < 1 || n > PatternGenAllPattern(params)) {
		return NULL;
	}
	while (n != params->count) {
		PatternGenNext(params);
	}
	return params->list;
}

extern int PatternGenHasNext(PatternGenParams *params) {
	int i;
	if (PatternGenCheckParams(params)) {
		return 0;
	}
	if (params->count == 0) {
		return 1;
	}
	for (i = 0; i < params->len; i++) {
		if (params->src[params->indexes[i]] 
				!= params->src[params->srcsize - i - 1]) {
			return 1;
		}
	}
	return 0;
}

const int* PatternGenNext(PatternGenParams *params) {
	int i, j, b, f;

	if (PatternGenCheckParams(params)) {
	 return NULL;
	}

	if (params->count == 0) {
		params->count++;
		return params->list;
	}
	 
	i = params->len - 1;
	params->flag[params->indexes[i]] = 0;
	 
	f = 1;
	 
	for (;;) {
		if (f) {
			b = params->src[params->indexes[i]];
			for (j = params->indexes[i] + 1; j < params->srcsize; j++) {
				if (params->flag[j] == 0 && params->src[j] != b) {
					break;
				}
			}
		} else {
			for (j = 0; j < params->srcsize; j++) {
				if (params->flag[j] == 0) {
					break;
				}
			}
			f = 1;
		}
		if (j == params->srcsize) {
			i--;
			if (i < 0) {
				PatternGenReset(params);
				break;
			} else {
				params->flag[params->indexes[i]] = 0;
			}
		} else {
			params->indexes[i] = j;
			params->list[i] = params->src[params->indexes[i]];
			params->flag[params->indexes[i]] = 1;
			i++;
			if (i == params->len) {
				// kakutei
				break;
			} else {
				f = 0;
			}
		}
	}
	params->count++;
	return params->list;
}

extern int PatternGenCount(PatternGenParams *params) {
	if (PatternGenCheckParams(params)) {
		return 0;
	}
	return params->count;
}

extern int PatternGenLength(PatternGenParams *params) {
	if (PatternGenCheckParams(params)) {
		return 0;
	}
	return params->len;
}

static int nCr(int n, int r) {
	int i, c;
	if (n < 0 || r < 0 || n < r) {
		return 0;
	}
	if (n - r < r) {
		r = n - r;
	}
	c = 1;
	for (i = 1; i <= r; i++) {
		c *= n;
		c /= i;
		n--;
	}
	return c;
}
 
static int nPr(int n, int r) {
	int p;
	if (n < 0 || r < 0 || n < r) {
		return 0;
	}
	p = 1;
	while (r > 0) {
		p *= n;
		n--;
		r--;
	}
	return p;
}
 

int main(void) {
	
	PatternGenParams params;
	PatternGenParams *gen = &params;
	const int *k;
	int i;
	
	PatternGenInitA(gen, 15);
	
	k = PatternGenGet(gen, 36690094);
	printf("%08d: ", PatternGenCount(gen));
	for (i = 0; i < PatternGenLength(gen); i++) {
		putchar("_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[k[i]]);
	} 
	putchar('\n');	
	
	PatternGenRelease(gen);
	
	return 0;
}