/*
	Usage:

		permute N P

	This program computes the P'th permutation of the set of integers from
	0 through N-1 inclusive.  The order of the permutations is
	implementation-dependent, but running with each P from 0
	through N!-1 will enumerate all the permutations.

	Link with gmp, the GNU multi-precision library.  For example:

		cc -o permute permute.c -lgmp
*/

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

int
main(int argc, char **argv)
{
	int rc;
	unsigned long elementsCount;
	mpz_t permutationIndex;
	mpz_t divisor, quotient, remainder;
	unsigned long i;
	unsigned long *elements;

	if (argc != 3) {
		fprintf(stderr, "Usage: %s N P\n", argv[0]);
		fprintf(stderr, "  N = number of elements\n");
		fprintf(stderr, "  P = permutation number [0 .. N!-1]\n");
		exit(1);
	}

	rc = sscanf(argv[1], "%lu", &elementsCount);
	if (rc != 1) {
		fprintf(stderr, "could not parse element count \"%s\"\n", argv[1]);
		exit(1);
	}
	if (elementsCount < 1) {
		fprintf(stderr, "invalid element count %lu; must be >= 1\n", elementsCount);
		exit(1);
	}

	rc = mpz_init_set_str(permutationIndex, argv[2], 0);
	if (rc < 0) {
		fprintf(stderr, "invalid permutation number \"%s\"\n", argv[2]);
		exit(1);
	}

	elements = calloc(elementsCount, sizeof *elements);
	if (elements == NULL) {
		fprintf(stderr, "calloc returned NULL\n");
		exit(1);
	}

	for (i = 0; i < elementsCount; i++) {
		elements[i] = i;
	}

	mpz_init(divisor);
	mpz_init(quotient);
	mpz_init(remainder);

	for (i = elementsCount; i > 0; i--) {
		unsigned long position;

		mpz_set_si(divisor, i);
		mpz_tdiv_qr(quotient, remainder, permutationIndex, divisor);

		position = mpz_get_ui(remainder);
		printf("%lu ", elements[position]);
		elements[position] = elements[i - 1];

		mpz_set(permutationIndex, quotient);
	}

	puts("");
	exit(0);
}