TAOCP 3.4.2 Exercise 15
Algorithm P begins with X_k=k,\qquad 1\le k\le t, and executes steps P2, P4 only until $j=t-n$.
Section 3.4.2: Random Sampling and Shuffling
Exercise 15. ▶ [30] (Ole-Johan Dahl.) If $X_k = k$ for $1 \le k \le t$ at the start of Algorithm P, and if we terminate the algorithm when $j$ reaches the value $t - n$, the sequence $X_{t-n+1}, \ldots, X_t$ is a random permutation of a random combination of $n$ elements. Show how to simulate the effect of this procedure using only $O(n)$ cells of memory.
Verified: yes
Solve time: 1m32s
Setup
Algorithm P begins with
$$ X_k=k,\qquad 1\le k\le t, $$
and executes steps P2, P4 only until $j=t-n$. Thus the exchanges are performed for
$$ j=t,t-1,\ldots,t-n+1. $$
After the last exchange, the entries
$$ X_{t-n+1},\ldots,X_t $$
form a random permutation of a random $n$-element subset of ${1,\ldots,t}$.
The problem is to produce the same distribution while using only $O(n)$ memory cells instead of storing all $t$ values $X_1,\ldots,X_t$.
Solution
During the truncated execution of Algorithm P, only positions
$$ t-n+1,\ldots,t $$
are ever used as the right-hand members of exchanges. Therefore the final answer depends only on the contents of these $n$ positions.
Let
$$ L=t-n+1. $$
For every position $i\ge L$ we store its current value explicitly in an array
$$ Y[L],Y[L+1],\ldots,Y[t]. $$
Initially,
$$ Y[i]=i,\qquad L\le i\le t. $$
When Algorithm P reaches a value $j$, it chooses
$$ k\in{1,\ldots,j} $$
uniformly and exchanges $X_k$ with $X_j$.
The difficulty is that $k$ may be less than $L$, corresponding to a position not explicitly stored. To represent such positions, maintain a dictionary $D$ containing exactly those indices $i<L$ whose current values differ from their original values. The current value at any position is therefore
$$ V(i)= \begin{cases} Y[i], & i\ge L,\[2mm] D(i), & i<L\text{ and }i\in D,\[2mm] i, & i<L\text{ and }i\notin D. \end{cases} $$
For each
$$ j=t,t-1,\ldots,L, $$
perform the following operations.
Choose $k$ uniformly from ${1,\ldots,j}$.
Let
$$ a=V(k),\qquad b=Y[j]. $$
These are the values that Algorithm P would exchange.
After the exchange, position $j$ receives $a$; hence set
$$ Y[j]\leftarrow a. $$
If $k<L$, position $k$ receives $b$. Therefore:
$$ D(k)\leftarrow b $$
when $b\ne k$, and delete the entry for $k$ when $b=k$.
If $k\ge L$, then $k$ is another stored position. Since $j$ is processed only once and will never again appear as a possible value of $k$, it suffices to place $b$ into position $k$ by setting
$$ Y[k]\leftarrow b. $$
When the loop terminates, output
$$ Y[L],Y[L+1],\ldots,Y[t]. $$
These values are exactly the contents of positions
$$ X_{t-n+1},\ldots,X_t $$
that would have resulted from the truncated execution of Algorithm P.
The array $Y$ contains $n$ entries. The dictionary $D$ contains entries only for indices below $L$ that have been involved in an exchange with one of the positions $L,\ldots,t$. Each iteration can create at most one new dictionary entry, and there are exactly $n$ iterations. Hence
$$ |D|\le n. $$
The total memory requirement is therefore at most
$$ n+n=2n $$
cells, which is $O(n)$.
Verification
At every stage define $V(i)$ as above. Initially,
$$ V(i)=i $$
for all $i$, matching the initial state of Algorithm P.
Assume inductively that immediately before a given exchange, $V(i)$ equals the value stored in position $i$ of Algorithm P. The algorithm selects the same random integer $k$ and computes
$$ a=V(k),\qquad b=V(j)=Y[j]. $$
Algorithm P exchanges these two values. The update rules place $a$ into position $j$ and $b$ into position $k$, leaving all other positions unchanged. Therefore the new function $V$ again coincides with the state of Algorithm P after the exchange.
By induction, the correspondence holds after every iteration. When the process stops, the stored entries
$$ Y[L],\ldots,Y[t] $$
are exactly the values of
$$ X_{t-n+1},\ldots,X_t $$
in the truncated Algorithm P. Consequently the output has precisely the same distribution, namely a random permutation of a random combination of $n$ elements.
This completes the proof.
∎
Notes
The method is a sparse simulation of the Fisher-Yates shuffle. Positions below $t-n+1$ are represented implicitly by the identity mapping except where an exchange forces a deviation. Since only $n$ exchanges are performed, at most $n$ such deviations need to be remembered. Thus the memory usage remains proportional to $n$, independent of $t$.