Given a string S of length n and a positive integer k <= n, we want to randomly, and with equal probability, choose a string from the set of all strings of length k that may be formed with a subset of the letters of S. For example, if S = daddy and k = 2, we want to choose each of the strings da, dd, dy, ad, ay, yd and ya with equal probability 1/7.

Obviously, one could do this by calculating all possible permutations. However, is there a more efficient way?

  • $\begingroup$ Nice question. The best algorithm might depend on which parameters we expect to be large. Are $n, k$ large and the number of possible letters is small (like $26$)? Or might all three be large? $\endgroup$ – 6005 Mar 26 at 0:55

Let $l$ be the number of distinct characters in the input string. So our input size is summarized by $n, k, l$, with $k \le n$ and $l \le n$.

Here is one efficient way to do it. In the first step, since the order of characters in the string doesn't matter, let's turn it into a map: $$ M = \{a \mapsto 1, d \mapsto 3, y \mapsto 1\}. $$ The idea of our algorithm is to first calculate the number of possible permutations of $k$ elements from $M$, and then to use this to generate one randomly.

Step 1: calculating the number of possible permutations

We use dynamic programming. We actually calculate, more generally, the quantity $$ p[i,j] \qquad \text{ for } 0 \le i \le k \text{ and } 0 \le j \le l, $$ which represent the *number of permutations of length $i$, which use only the first $j$ elements of the map. For example, in the example problem (input "daddy", $k = 2$), we have \begin{align*} p[0, 0] &= p[0, 1] = p[0, 2] = p[0, 3] = 1 \quad \text{(empty string)} \\ p[1, 1] &= 1 \quad \text{(strings of length 1 using only a -- so just "a")} \\ p[1, 2] &= 2 \quad \text{(strings of length 1 using a and d -- so "a" and "d")} \\ p[1, 3] &= 3 \quad \text{("a", "d", and "y")} \\ p[2, 1] &= 0 \quad \text{(no strings of length two using only a since only one a is allowed)} \\ p[2, 2] &= 3 \quad \text{("ad", "da", and "dd")} \\ p[2, 3] &= 7 \quad \text{("ad", "da", "dd", "ay", "ya", "dy", "yd")} \end{align*}

Now how do we calculate $p$? We can use a recursive algorithm. Let $M[j]$ denote the value of $M$ on the $j$th character (so in our example, $M[1] = 1, M[2] = 3, M[3] = 1$). Then $$ p[i, j] = \sum_{i' = 0}^{M[j]} \binom{i}{i'} p[i - i', j-1]. $$

What this formula says is: pick $i'$ places to put character $j$. For example, in our running example for $p[2, 3]$, it says pick $i'$ places to put the character $y$ in a string of length $2$. Then for the remaining $i- i'$ places, we fill them in with a string only using the first $j-1$ characters (which can be done in $p[i-i', j-1]$ ways). The variable $i'$ ranges from $0$ to $M[j]$ because we can only use character $j$ at most $M[j]$ times.

This recurrence allows us to calculate the entire table of $p[i,j]$ in approximately $O(nk)$ time.

Step 2: Picking a permutation at random

The total number of permutations is $p[k, l]$. So pick a random number $r$ from $1$ to $p[k, l]$.

Now recall the recurrence relation $$ p[i, j] = \sum_{i' = 0}^{M[j]} \binom{i}{i'} p[i - i', j-1]. $$

Very roughly, we can use this recurrence relation to enumerate the $r$th permutation. To evaluate the $r$th permutation of $p[i,j]$ total, evaluate the above sum and locate the term where the $r$th permutation would fall. For example if $r = 4$ and there are $7$ total permutations, and the sum gives you $3 + 4$, then $4$ falls fourth out of $7$, so it falls in the second group. Then, we are looking for the first out of $4$ permutations in the second group, which we can recursively find by picking a random permutation from $p[i - i', j-1]$.

| cite | improve this answer | |

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.