# Generate ordered stream of $n$ random integers in a given range using $O(1)$ space (reference request)

I'm looking for a reference to an algorithm that does the following. Given n, and a range [min, max], generate a random ascending stream of n integers i_1, i_2 .. i_n such that min <= i_1 < i_2 < ... < i_n <= max. And this should be done in constant space.

(So I'm looking for a more efficient alternative to the following simple approach: First generate n random numbers in the desired range, then sort them, and then go over the sorted list in order. This needs O(n) space.)

I could swear I saw a paper describing an algorithm that does exactly this. But I can't find that paper again, no matter what I search for. Am I misremembering? Can you help me?

• I don't think you can achieve a sorted stream of i.i.d variables without generating them all first: the next number you generate can always be the smallest! Hence, I think you need to check which exact random model you're supposed to provide there. – Raphael Oct 14 '17 at 12:37
• What might be possible is, given the desired model, to determine Pr[a[i] = k | a[1], ..., a[i-1]] in that model, with a[i] the i-th element in the sorted sequence. (Use order statistics.) Then you can generate one element after another using this distribution. – Raphael Oct 14 '17 at 12:39
• "generating n random numbers normally" -- with what distribution? That's going to be crucial here. – Raphael Oct 14 '17 at 14:15
• @Raphael: Just the uniform distribution between min and max. (Though actually, that can result in duplicates. Haven't thought that part through...) – user12186 Oct 14 '17 at 19:58
• D.W.'s answer does uniformly without replacement, so no duplicate. But not i.i.d. uniformly. – Raphael Oct 15 '17 at 4:24

It can be done in $O(1)$ space and $O(n^2)$ time. Let $X_1,\dots,X_n$ denote the numbers in the stream, in sorted order. You can calculate

$$\Pr[X_i = x_i | X_1=x_1,\dots,X_{i-1}=x_{i-1}]$$

and then use that to generate the numbers $X_1,\dots,X_n$ one by one.

Here is the derivation. We have

\begin{align*} \Pr[X_1=x_1,\dots,X_{i-1}=x_{i-1}] &= {{\text{max}-x_{i-1} \choose n-i+1} \over {\text{max}-\text{min}+1 \choose n}}\\ \Pr[X_1=x_1,\dots,X_{i-1}=x_i] &= {{\text{max}-x_i \choose n-i} \over {\text{max}-\text{min}+1 \choose n}} \end{align*}

so it follows that

$$\Pr[X_i = x_i | X_1=x_1,\dots,X_{i-1}=x_{i-1}] = {{\text{max}-x_i \choose n-i} \over {\text{max}-x_{i-1} \choose n-i+1}}= \Pr[X_i = x_i | X_{i-1}=x_{i-1}].$$

Here the domain of possible values for $X_i$ is $x_{i-1}+1,\dots,\text{max}$; the probability is zero for other values of $X_i$ outside that domain.

Notice that this probability depends only on $x_{i-1},x_i$, so you only need a constant amount of space: you don't need to remember the entire past history.

Thus, the algorithm becomes:

1. Pick $x_1$ from the distribution $\Pr[X_1=x_1] = {{\text{max}-x_1 \choose n-1} \over {\text{max}-\text{min}+1 \choose n}}$.

2. For each $i=2,3,\dots,n$, pick $x_i$ from the distribution for $\Pr[X_i = x_i | X_{i-1}=x_{i-1}]$ given above.

This algorithm requires only $O(1)$ space. The running time might be $O(n^2)$ (since it might take $O(n)$ time to draw from a distribution with $n$ possible values). Perhaps further analysis could reduce the running time by finding a more efficient way to draw from these distributions. For instance, if you could find a way to compute the cdf (cumulative distribution function) for these distributions and evaluate it at an arbitrary $x_i$ in $O(1)$ time, then you could reduce the total running time to $O(n \log n)$ by using binary search at each step to draw from the distribution. I don't see how to do that myself, but perhaps someone else will.

This might get a lot easier if you are willing to draw streams of non-decreasing integers rather than a stream of increasing integers (i.e., allow an integer to be repeated), since the formulas for probability for drawing with replacement tend to be a lot simpler than those for drawing without replacement.

• So that quick idea of mine actually works out? X-) Cool, thanks! – Raphael Oct 14 '17 at 20:30
• "The running time might be O(n²) (since it might take O(n) time to draw from a distribution with n possible values)" -- I think Knuth had something nice in TAOCP on this. – Raphael Oct 15 '17 at 4:24

Original asker here. For anyone else looking at this: the paper I was looking for is Generating Sorted Lists of Random Numbers by Jon Louis Bentley and James B. Saxe. The algorithm in the paper does what I asked.

• I'm not sure the problems are equivalent. The question here is about integers, while the paper refers to floating point numbers. How can you adapt Bentley's algo to integers? – Eyal Schneider Jul 9 at 10:51
• – Eyal Schneider Jul 9 at 13:10