# Sampling of subsets with repeat

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?

• 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?
– 6005
Mar 26 '20 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]$$.