Efficient algorithm to find the nth number in a base-k numeral system with only different digits

Question

I am looking for an efficient algorithm for the following problem.

There is a base-k numeral system, and we want to have some k-length numbers, but all of the digits must be different ones.

It would be useful, if all of the possible feasible numbers would be unequivocal sortable (so the given nth number is always the same one).

An example to be clear:

k=5

possible digits: 0 ... (k-1) -> 0, 1, 2, 3, 4

we have a base-5 numeral system

we need numbers with length 5

possible feasible numbers:

01234

10234

02134

...

43210

The goal is, to find a way, that if I say, I need the 8th number, it will give me for example 34210 (and it will give me always this number, if I ask for the 8th one).

It is also important, that this algorithm should be efficient, if it is possible in O(1), or in P.

It would be also great, if the algorithm would not generate and store all of the possible feasible solutions, but somehow it could generate only that one appropriate number, which is the answer for the input.

I guess, there is no known P solution for this.

The brute-force and probably not the most efficient way would be, to generate and store all of the possible feasible solutions in a given order, and then we could answer any input, and the same input would generate always the same output. This solution satisfies all of the above criteria, but maybe there is a much more efficient algorithm to do this.

Answer 1

Your problem is known as unranking permutations in lexicographic order. Bonet, Efficient Algorithms to Rank and Unrank Permutations in Lexicographic Order describes efficient algorithms, and contains some pointers to the literature.

As described in the paper, more efficient algorithms are possible if you don't insist on lexicographic order.