**Problem Detail:**

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`

.

- I want to know the number of different strings with length $l$ using these characters (but no more than the available copies).
- 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?

###### Asked By : mickeyandkaka

#### Answered By : Yuval Filmus

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.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65110

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback