#include <iostream>
#include <cstring>
using namespace std;

class PatternGeneratorException {};

class PatternGenerator
{
private:
	int *_src;
	int *_flag;
	int *_indexes;
	int *_list;
	int _srcsize;
	int _len;
	int _count;
	int _all;
	
	PatternGenerator() {}
	
	PatternGenerator(int srcsize, int len, int a) 
				: _srcsize(srcsize), _len(len), _all(a) {

		if (_srcsize < 2 || _len < 2 || _srcsize < _len) {
			throw PatternGeneratorException();
		}		
		_src = new int[_srcsize];
		_flag = new int[_srcsize];

		_list = new int[_len];
		_indexes = new int[len];
		
		for (int i = 0; i < _srcsize; i++) {
			_flag[i] = 0;
		}		
	}
public:

	static int nCr(int n, int r);
	static int nPr(int n, int r);

	PatternGenerator(int srcsize, int len) 
			: PatternGenerator(srcsize, len, 0) {

		for (int i = 0; i < _srcsize; i++) {
			_src[i] = i + 1;
		}		
		
		reset();
	}
	
	PatternGenerator(int size) 
			: PatternGenerator(size, size) {
	}
	
	PatternGenerator(const int *sortedsrc, int srcsize, int len)
			: PatternGenerator(srcsize, len, 0) {

		memcpy(_src, sortedsrc, sizeof(int) * _srcsize);
		
		reset();
	}
	
	~PatternGenerator() {
		delete [] _src;
		delete [] _flag;
		delete [] _list;
		delete [] _indexes;
	}
	
	int length()     const { return _len; }
	int sourcesize() const { return _srcsize; }
	int count()      const { return _count; }
	const int* source() const { return _src; }
	
	void reset() {
		for (int i = 0; i < _len; i++) {
			_flag[_indexes[i]] = 0;
		}
		for (int i = 0; i < _len; i++) {
			_indexes[i] = i;
			_list[i] = _src[_indexes[i]];
			_flag[_indexes[i]] = 1;
		}
		_count = 0;
	}
	
	int allpattern() {
		if (_all == 0) {
			_all = nCr(_srcsize, _len) * nPr(_len, _len);
			int c = 0;
			for (int i = 1; i < _srcsize; i++) {
				if (_src[i - 1] == _src[i]) {
					c++;
				} else {
					if (c) {
						c++;
						_all /= nPr(c, c);
						c = 0;
					}
				}
			}
			if (c) {
				_all /= nPr(c, c);
			}
		}
		return _all;
	}
	
	const int* get(int n) {
		if (n < 1 || n > allpattern()) {
			throw PatternGeneratorException();
		}
		while (n != _count) {
			next();
		}
		return _list;
	}
	
	int hasNext() {
		if (_count == 0) {
			return 1;
		}
		for (int i = 0; i < _len; i++) {
			if (_src[_indexes[i]] != _src[_srcsize - i - 1]) {
				return 1;
			}
		}
		return 0;
	}
	
	const int* next() {
		
		if (_count == 0) {
			_count++;
			return _list;
		}
		
		int i, j, b, f;
		
		i = _len - 1;
		_flag[_indexes[i]] = 0;
		
		f = 1;
		
		for (;;) {
			if (f) {
				b = _src[_indexes[i]];
				for (j = _indexes[i] + 1; j < _srcsize; j++) {
					if (_flag[j] == 0 && _src[j] != b) {
						break;
					}
				}
			} else {
				for (j = 0; j < _srcsize; j++) {
					if (_flag[j] == 0) {
						break;
					}
				}
				f = 1;
			}
			if (j == _srcsize) {
				i--;
				if (i < 0) {
					reset();
					break;
				} else {
					_flag[_indexes[i]] = 0;
				}
			} else {
				_indexes[i] = j;
				_list[i] = _src[_indexes[i]];
				_flag[_indexes[i]] = 1;
				i++;
				if (i == _len) {
					// kakutei
					break;
				} else {
					f = 0;
				}
			}
		}
		_count++;
		return _list;
	}
};

int PatternGenerator::nCr(int n, int r) {
	if (n < 0 || r < 0 || n < r) {
		return 0;
	}
	if (n - r < r) {
		r = n - r;
	}
	int c = 1;
	for (int i = 1; i <= r; i++) {
		c *= n;
		c /= i;
		n--;
	}
	return c;
}

int PatternGenerator::nPr(int n, int r) {
	if (n < 0 || r < 0 || n < r) {
		return 0;
	}
	int p = 1;
	while (r > 0) {
		p *= n;
		n--;
		r--;
	}
	return p;
}

int main() {
	int src[] = { 1, 2, 2, 5};
	int len = sizeof(src) / sizeof(src[0]);
	PatternGenerator gen(15);
	PatternGenerator gen2(5, 3);
	PatternGenerator gen3(src, len, len);
	
	cout << "all pattern: " << gen.allpattern() << endl;
	cout << "all pattern 2: " << gen2.allpattern() << endl;
	cout << "all pattern 3: " << gen3.allpattern() << endl;
	
	const int *kk = gen.get(36690094);
	cout.fill('.');
	cout.width(8);
	cout << gen.count() << ": ";
	for (int i = 0; i < gen.length(); i++) {
		cout << "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"[kk[i]];
	}
	cout << endl << endl;
	
	int src2[] = { 1, 2, 2, 2, 5, 7, 7, 9};
 	int len2 = sizeof(src2) / sizeof(src2[0]);
	PatternGenerator gen4(src2, len2, len2);

	cout << "all pattern 4: " << gen4.allpattern() << endl;
 	
 	while (gen4.hasNext()) {
 		const int *k = gen4.next();
 		cout.fill('_');
 		cout.width(8);
 		cout << gen4.count() << ": ";
 		for (int i = 0; i < gen4.length(); i++) {
 			cout << k[i];
 		}
 		cout << endl;
 	}
 	
	
	return 0;
}