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?

Improve this question
$\endgroup$
8
  • 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 22:24

1 Answer 1

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

Improve this answer
$\endgroup$

Your Answer

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

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