3
$\begingroup$

The origin problem is here. Now it is deleted.

Suppose I have 3 'available' copies of a, 2 of b, 3 of c, and 4 of d.

  1. I want to know the number of different strings with length $l$ using these characters (but no more than the available copies).
  2. Is there an efficient (i.e. $o(k)$) algorithm for computing the $k$-th smallest string of length $l$ in lexicographic order?

For example, The first string of length 1 is a, the second string of length 3 is aab, the 5th string of length 5 is aaacc (following aaabb, aaabc, aaabd, and aaacb), etc.

What kind of algorithm or math can I use to calculate?

$\endgroup$
  • 1
    $\begingroup$ Please do not cross-post. If you have decided to move your question from Math it should be migrated or doing so manually you should delete the previous one. $\endgroup$ – Evil Oct 25 '16 at 16:26
  • $\begingroup$ It's midnight in China, I will close the origin problem at math tomorrow. By the way, k=1 the answer is 4, k=2 the answer is 16, k=3 the answer is 63(except bbb). $\endgroup$ – mickeyandkaka Oct 25 '16 at 16:38
  • $\begingroup$ @Evil It certainly shouldn't be $k-th$, since that denotes the difference between $k$ and the product of $t$ and $h$. To be honest, I'd typeset it as just $k$th -- one doesn't use a hyphen in "4th", for example. $\endgroup$ – David Richerby Oct 25 '16 at 20:26
  • 2
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/65110/755, math.stackexchange.com/q/1984522/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Oct 25 '16 at 21:50
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Oct 25 '16 at 22:24
4
$\begingroup$

You are asking two questions. The first is an enumeration question, and the second is about generation or encoding/decoding. The enumeration question is a standard combinatorial exercise, which can be solved using exponential generating functions (and algorithmically, using dynamic programming). For example, the number of strings of length $\ell$ in your example is $\ell!$ times the coefficient of $x^\ell$ in the exponential generating function $$ \left(1 + x + \frac{x^2}{2!}\right) \left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!}\right)^2 \left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}\right). $$

For the generation problem, the idea is as follows. Suppose that we want the $k$th lexciographically smallest string of length $\ell$. We will uncover the letters one by one. To find the first letter, we count how many strings of length $\ell$ start with each letter—an instance of the enumeration problem mentioned above—and use this information to determine the first letter. We find the subsequent letters in a very similar way.

$\endgroup$

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.