patternMinor
Randomly filling an $n$-length array with values from $0$ to $k$ that total to $0 < m < nk$ - is a linear-time algorithm possible?
Viewed 0 times
totallineararraywithlengthtimerandomlyfillingalgorithmthat
Problem
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?
$$[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?
Solution
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]$).
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]$).
Context
StackExchange Computer Science Q#90314, answer score: 4
Revisions (0)
No revisions yet.