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;
}