Randomly filling an $n$-length array with values from $0$ to $k$ that total to $0 < m < nk$ - is a linear-time algorithm possible?

Question

Let $n, k > 0$ and $0 < m < nk$. I want to fill an $n$-length array $A$ with random integer values in the range $[0,k]$ such that $\sum_{i=0}^{n -1} A[i] = m$. Furthermore, all such arrays should be equally likely (that is, any valid array should occur with equal probability to any other). For example, if $n = 3, k = 2, m = 3$, any of these results should be equally likely:

$$[0,1,2]$$ $$[0,2,1]$$ $$[1,1,1]$$ $$[2,1,0]$$ $$[1,2,0]$$ $$[1,0,2]$$ $$[2,0,1]$$

The closest solution I could find was this, which is $O(n)$ assuming that we use a linear-time sort and shuffle (such as radix sort and Fisher-Yates respectively). However, this approach does not limit what the integers in each array position can be. Is there a $O(n)$ algorithm which solves the version of this problem described above?

Answer 1

Once you know how to count the number of such arrays, you can turn that into a procedure to generate a random such array, using ranking/unranking procedures.

Let's see how to count them. Let $f(k,m,n)$ denote the number of such arrays. Note that we have

$$f(k,m,n) = \sum_{x=0}^k f(k,m-x,n-1)$$

by enumerating all possibilities for $A[0]$. So, this gives a dynamic programming algorithm to count the number of such arrays.

How does this lead to a way to generate a random array? Well, in counting such arrays, we've implicitly established a bijection $\varphi$ from the set of such arrays to the set of integers $\{0,1,2,\dots,f(k,m,n)-1\}$. So, we just need a way to compute $\varphi^{-1}$, and then we have a way to pick a random array: we pick a random number between $0$ and $f(k,m,n)-1$, then apply $\varphi^{-1}$ to obtain the corresponding array.

Now the recurrence above establishes such a bijection. In particular, the arrays that start with $A[0]=0$ correspond to integers in the range $0 .. f(k,m,n-1)-1$, the arrays that start with $A[0]=1$ correspond to integers in the range $f(k,m,n-1)..f(k,m,n-1)+f(k,m-1,n-1)-1$, and so on. So, given a random integer $y$, we find the smallest $x_0$ such that

$$y < \sum_{x=0}^{x_0} f(k,m-x,n-1),$$

and then set $A[0]=x_0$ and continue recursively to fill in the rest of the array (replacing $y$ with $y' = y - \sum_{x=0}^{x_0-1} f(k,m-x,n-1)$ and using $y'$ to fill in the array $A[1..n-1]$).