/*
	順列とはモノの順番付きの並びのことである. 
	たとえば, 3124は数1, 2, 3, 4の一つの順列である. 
	すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると

	012 021 102 120 201 210
	になる.

	0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目を答えよ
*/

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

#define N 1000000


/* 表示。*/
void printArray(int array[], int size) {
	int i;

	for ( i = 0; i < size; i++ ) {
		printf("%d ", array[i]);
	}
	printf("\n");
}


/* この問題でしか使えない(0から始まり連続する数列)順列生成。*/
// 1回呼ぶと1回入れ替える。
int nextPermutation(int array[], int size, int last) {
	// flagAryはarray[]に0があるのでしょうがなく用意。
	// ↑tmpAry[]の初期値0と被るので。
	// 一時領域内に存在する数(初期値でない0含む)の場所でフラグを立てる。
	int *flagAry, *tmpAry, *tmpPtr;
	int tmp;
	int i, j, now, cnt = 0;

	tmpPtr = array;

	// 配列の最後から調べる。
	now = size-1;

	flagAry = (int *)malloc(sizeof(int)*size);
	if( flagAry == NULL ) {
		printf("メモリ確保失敗。\n");
		exit(0);
	}
	for( i = 0; i < size; i++ ) {
		flagAry[i] = 0;
	}

	tmpAry = (int *)malloc(sizeof(int)*size);
	if( tmpAry == NULL ) {
		printf("メモリ確保失敗。\n");
		exit(0);
	}
	for( i = 0; i < size; i++ ) {
		tmpAry[i] = 0;
	}

	// 1回入れ替えるまでループ。
	for(;;) {

		// 一時領域内に自分より多い数があるか調べる。
		for( i = 0; i < size && tmpAry[i] <= array[now]; i++ ) {
			;
		}

		// なかったら一時領域内で一番小さい数と自分を入れ替える。
		if( i != size ) {
			tmp = array[now]; array[now] = tmpAry[i]; tmpAry[tmp] = tmp;

			// フラグ立てたり下ろしたり。
			tmpAry[i] = 0;
			flagAry[i] = 0;
			flagAry[tmp] = 1;

			// 配列に入れてない残りの数を入れる。
			// 昇順に入れるんだけど、もともとflagAry[]は昇順だからソート不要。
			for( i = 0, j = now+1; i < size; i++ ) {
				if( flagAry[i] == 1 ) {
					array[j] = i;
					j++;
				}
			}
			free(flagAry);
			free(tmpAry);
			return 1;

		// あったら一時領域内に入れてフラグを立てる。
		} else {
			tmpAry[array[now]] = array[now];
			flagAry[array[now]] = 1;
		}

		// 生成前後の数列の並びをチェック。
		// この関数に呼ばれたとき、array[]が9876543210のときにのみ、
		// size回カウントされる(並び替え終わると0123456789になるから。
		for( ; last >= 0; last--, tmpPtr++ ){
			if( last == *tmpPtr ) {
				cnt++;
			}
		}
		if( cnt == size ) {
			free(flagAry);
			free(tmpAry);
			return 0;
		}

		// ここに来たときは、並び替えが完了してない。
		// 調べる配列の要素番号を1つ小さくしてもっかい。
		now--;
	}
}


int main(void) {
	int num[] = {0,1,2,3,4,5,6,7,8,9};
	int size = sizeof(num)/sizeof(num[0]);
	int last = num[size-1];
	int cnt = 0;

	do {
		//printArray(num, size);
		if( ++cnt == N ) break;
	} while( nextPermutation(num, size, last) );


	printArray(num, size);

	return 0;
}

2 7 8 3 9 1 5 4 6 0