24問目

順列は順序が付いた物の並べ替えのことである. 例えば, 3124 というのは 1, 2, 3, 4 という数字の順列の一つである. 全ての順列が数字順もしくはアルファベット順に並んでいるとき, それを「辞書順(lexicographic order)」と呼ぶ. 0, 1, 2 の順列を辞書順に並べたものは,
012, 021, 102, 120, 201, 210
です.
では, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 の順列のうち, 辞書順で1,000,000番目の順列は何か?

http://projecteuler.net/index.php?section=problems&id=24

以前, レイトン教授シリーズに出てきた 8queen puzzle を解くために作った permut 関数があるのでそれを使用. 実装が面倒なところはそこだけなので, あっけなく終わりました.

/* Problem024.c */
#include <stdio.h>
#include "permut.h"

#define ORDER 1000000
#define NUM 10

int main() {
	int array[NUM] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
	int i;

	permut(array, NUM, ORDER - 1);

	fprintf(stdout, "Solution: ");
	for (i = 0; i < NUM; i++) {
		fprintf(stdout, "%d", array[i]);
	}
	fprintf(stdout, "\n");

	return 0;
}

permut.c の中で malloc しているところが不要だなぁ, と思っているので, 今後直す予定です.

/* permut.c */
#include "permut-1.0.h"
#define DEBUG 0

int permut(int *sequence, int size, int index)
{
	int tempIndex, mainIndex;
	int *memo, *memoIndex;

	#if DEBUG
	printf("\n\nindex=%d:", index);
	#endif

	if ((memo = malloc(size * sizeof(int))) == NULL) {
		printf("Error: failed to malloc.\n");
		return EXIT_FAILURE;
	}

	if ((memoIndex = malloc(size * sizeof(int))) == NULL) {
		printf("Error: failed to malloc.\n");
		return EXIT_FAILURE;
	}

	for (mainIndex = 0; mainIndex < size; mainIndex++) {
		memo[mainIndex] = mainIndex;
	}

	for (mainIndex = 0; mainIndex < size; mainIndex++) {
		tempIndex = index % (mainIndex + 1);
		index /= (mainIndex + 1);
		memoIndex[size - mainIndex - 1] = tempIndex;
	}
	assert(index == 0);

	#if DEBUG
	printf("\ntempIndex=");
	#endif
	for (mainIndex = 0; mainIndex < size; mainIndex++) {
		tempIndex = memoIndex[mainIndex];
		sequence[mainIndex] = memo[tempIndex];
		#if DEBUG
		printf("%d", tempIndex);
		#endif
		for (; memo[tempIndex] < size && tempIndex < size-1; tempIndex++) {
			memo[tempIndex] = memo[tempIndex + 1];
		}
	}

	#if DEBUG
	printf("\npermutation:");
	for (mainIndex = 0; mainIndex < size; mainIndex++) {
		printf("%d", sequence[mainIndex]);
	}
	printf("\n");
	#endif

	free(memo);
	free(memoIndex);
	return 0;
}