Exact Online Rank Recycling in Floyd's Uniform Subset Sampler

A uniformly random $m$-subset of $[n]=\{0,\dots ,n-1\}$ has entropy ${\log }_2\left(\genfrac{}{}{0px}{}{n}{m}\right)$. Standard without-replacement procedures often expose an additional ordering coordinate that is absent from the returned set. We show that Floyd’s subset sampler admits an exact round-local factorization of this coordinate. In round $r$, let $S$ be an $(r-1)$-subset of $[j]$, let $T\sim \mathrm{Unif}([j+1])$, and let $S^{\mathrm{\prime }}$ be the result of Floyd’s transition. If $D$ is the zero-based rank of the original draw $T$ in $S^{\mathrm{\prime }}$, then $(S,T)\leftrightarrow (S^{\mathrm{\prime }},D)$ is a bijection between $\left(\genfrac{}{}{0px}{}{[j]}{r-1}\right)\times [j+1]$ and $\left(\genfrac{}{}{0px}{}{[j+1]}{r}\right)\times [r]$. Consequently, $S^{\mathrm{\prime }}$ and $D$ are independent and uniform on their respective spaces. The digit $D$ can therefore be merged immediately into a residual uniform random state; an induction shows that the partial subset remains independent of that state after every round. For $k=\min (m,n-m)$, the sampling phase uses $O(k\log k)$ time and $O(k)$ auxiliary space with an order-statistic tree; explicitly materializing a complement incurs the unavoidable output cost. The combinatorial layer avoids binomial-coefficient arithmetic and recovers the complete $k!$ state-space factor exactly. We also give a finite counterexample showing that analogous immediate rank recycling in a partial Fisher-Yates array is invalid because the unselected suffix retains a correlated ordering. A 64-bit Rust implementation is checked by exhaustive state-space enumeration for all $n\le 8$ and by an entropy-accounting trace for choosing $\mathrm{20,000}$ of $\mathrm{30,000}$ items. We make no claim of runtime superiority over existing subset samplers.