4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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]$).

$\endgroup$
  • $\begingroup$ Totally unrelated problem, but the rank/unrank technique reminded me of this challenge I answered a year ago. The beauty is that it applies it recursively. $\endgroup$ – orlp Apr 7 '18 at 2:01
  • $\begingroup$ What're the base cases for $f(k,m,n)$ above? $\endgroup$ – Koz Ross Apr 7 '18 at 5:18
  • $\begingroup$ @KozRoss, I'm sure you can figure them out. If $m \le 0$ or $n \le 1$ I bet you can figure out what to use as the value of $f(k,m,n)$. $\endgroup$ – D.W. Apr 7 '18 at 17:59

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.