#include <iostream>
#include <iomanip> 

using namespace std;

class CombinationGeneratorException {};

class CombinationGenerator
{
private:
	int *_list;
	int *_stack;
	int _size;
	int _i, _j, _p, _c;
	int _all;
	CombinationGenerator();
public:
	CombinationGenerator(int size)
			: _size(size), _i(1), _j(0), _p(0), _all(0), _c(0) {
		if (_size < 2) {
			throw CombinationGeneratorException();
		}
		_list = new int[_size];
		_stack = new int[_size];
	}
	~CombinationGenerator() {
		delete [] _list;
		delete [] _stack;
	}
	
	void init(int size) {
		if (size < 2) {
			throw CombinationGeneratorException();
		}
		if (size > _size) {
			delete [] _list;
			delete [] _stack;
			_list = new int[size];
			_stack = new int[size];
		}
		_size = size;
		_all = 0;
		_i = 1;
		_j = _p = _c = 0;
	}
	
	void reset() {
		for (_j = 0; _j < _size; _j++) {
			_list[_j] = 0;
		}
		_i = 1;
		_j = 0;
		_p = 0;
		_c = 0;
	}
	
	int hasNext() {
		return _c != allpattern();
	}
	
	const int* get(int idx) {
		if (idx < 1 || idx > allpattern()) {
			throw CombinationGeneratorException();
		}
		while (_c != idx) {
			next();
		}
		return _list;
	}
	
	const int* next() {
		if (_i > _size) {
			_list[_j] = 0;
			_j++;
			_i--;
		}
		for (;;) {
			while (_j == _size) {
				_i--;
				if (_i < 1) {
					_i = 1;
					_j = 0;
					_p = 0;
					_c = 0;
				} else {
					_p--;
					_j = _stack[_p];
					_list[_j] = 0;
					_j++;
				}
			}
			if (_list[_j] == 0) {
				_list[_j] = _i;
				_i++;
				if (_i > _size) {
					_c++;
					break;
				} else {
					_stack[_p] = _j;
					_p++;
					_j = 0;
				}
			} else {
				_j++;
			}
		}
		return _list;
	}
	
	int length() const {
		return _size;
	}
	
	int allpattern() {
		if (_all == 0) {
			_all = 1;
			for (int i = 2; i <= _size; i++) {
				_all *= i;
			}
		}
		return _all;
	}
};


int main() {
	
	try {
		CombinationGenerator gen(4); 
		
		cout << "all pattern: " << gen.allpattern() << endl;
		
		for (int j = 0; j <= gen.allpattern(); j++) {

			cout << setfill(' ') << setw(4) << (j + 1) << ": ";

			const int *k = gen.next();

			for (int i = 0; i < gen.length(); i++) {
				cout << "_ABCDEFG"[k[i]];
			}

			cout << endl;
		}
		
		cout << endl;
		
		gen.reset();
		while (gen.hasNext()) {
			const int *k = gen.next();
			for (int i = 0; i < gen.length(); i++) {
				cout << "_ABCDEFG"[k[i]];
			}
			cout << endl;
		}
		
		cout << endl;
		
		cout << setfill('0') << setw(4) << 18 << ": ";
		for (int i = 0; i < gen.length(); i++) {
			cout << "_ABCDEFG"[gen.get(18)[i]];
		}
		cout << endl;

	} catch (CombinationGeneratorException& ex) {
		cout << "error" << endl;
	}
	
	return 0;
}