# Computing $n$th lexicographically smallest permutation of length up to $k$

I wonder how to tackle such problem, to be more specific:

Given a set and an integer $k$, find the $n$th lexicographically smallest permutation (with repetitions allowed) of the set. We will say that the permutation is valid if its length is up to $k$ (inclusive).

Here's an example: $S$ = {a, b, c}, $k$ = 4, $n$ = 15

a aa aaa aaaa aaab aaac aab aaba aabb aabc aac aaca aacb aacc ab

Output should be: "ab" as it's the n-th lexicographically smallest permutation of length up to k of this set.

How to do this efficiently?

• I don't understand the problem. In my book a permutation of a set always has the same length. Perhaps you could give an example? – Yuval Filmus Nov 18 '16 at 11:39
• And I don't understand what you mean by "permutation (with repetitions allowed) of [a] set". Sets don't have repetitions, and permutations are bijective so you can't create repetitions by permuting something that doesn't already have them. – David Richerby Nov 18 '16 at 11:47
• But, whatever it is you're looking for, computing permutations and permutation-like objects is a fairly standard problem. So what research did you do before asking here? – David Richerby Nov 18 '16 at 11:48
• See also Knuth TAoCP 7.2.1.2 Exercise 12. – András Salamon Nov 18 '16 at 17:11

Your kind of problem reduces to the problem of enumeration. For example, suppose that you wanted to know the first letter of the $n$th lexicographically smallest non-empty string of length at most $k$ over the alphabet $S$. You could easily solve that if you could calculate the number of strings of length at most $k$ that start with a given letter.
How many strings of length up to $k$ over the alphabet $S$ start with the prefix $w$?
• Talking about the harder version, I can't see a way other than keeping increment count and (somehow) generating strings on the fly as you go towards $k$. You don't even know how many strings there will be at all given how big $n$ can be. I don't want to take too much of your time, could you point me somewhere in the net for the detailed explanation of similar/exact problem? – user61633 Nov 18 '16 at 13:36