# 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. Commented Oct 14, 2017 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. Commented Oct 14, 2017 at 12:39
• "generating n random numbers normally" -- with what distribution? That's going to be crucial here. Commented Oct 14, 2017 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...) Commented Oct 14, 2017 at 19:58
• D.W.'s answer does uniformly without replacement, so no duplicate. But not i.i.d. uniformly. Commented Oct 15, 2017 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! Commented Oct 14, 2017 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. Commented Oct 15, 2017 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? Commented Jul 9, 2019 at 10:51
• Commented Jul 9, 2019 at 13:10