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?

Improve this question
$\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
    Commented Nov 18, 2016 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
    Commented Nov 18, 2016 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
    Commented Nov 18, 2016 at 11:48
  • $\begingroup$ See also Knuth TAoCP 7.2.1.2 Exercise 12. $\endgroup$
    – András Salamon
    Commented Nov 18, 2016 at 17:11

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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