Computing $n$th lexicographically smallest permutation of length up to $k$
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.

More generally, the enumeration problem you have to solve in your case is:


  How many strings of length up to $k$ over the alphabet $S$ start with the prefix $w$?


This is not such a hard problem, and I'll let you solve it on your own. I'll also let you figure out how to use the result in order to solve your problem.