2
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Nov 18 '16 at 11:39
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Nov 18 '16 at 11:47
  • $\begingroup$ 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? $\endgroup$ – David Richerby Nov 18 '16 at 11:48
  • $\begingroup$ See also Knuth TAoCP 7.2.1.2 Exercise 12. $\endgroup$ – András Salamon Nov 18 '16 at 17:11
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ What if I'll say that no two consecutive elements can be the same, will the logic still apply? $\endgroup$ – user61633 Nov 18 '16 at 12:54
  • $\begingroup$ Yes, but the enumeration problem will be slightly more difficult. $\endgroup$ – Yuval Filmus Nov 18 '16 at 12:55
  • $\begingroup$ 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? $\endgroup$ – user61633 Nov 18 '16 at 13:36
  • $\begingroup$ Unfortunately I am not aware of any online resources on this matter. $\endgroup$ – Yuval Filmus Nov 18 '16 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.