Generate ordered stream of $n$ random integers in a given range using $O(1)$ space (reference request)
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}] &amp;= {{\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] &amp;= {{\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:


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}}$.
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.