2026/07/15 by Yingqi Zhang
#cs.DS #cs.DM #cs.IT #math.IT
A uniformly random m-subset of [n]=\0,…,n-1\ has entropy log2\binomnm. 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\simUnif([j+1]), and let S' be the result of Floyd's transition. If D is the zero-based rank of the original draw T in S', then (S,T)↔(S',D) is a bijection between \binom[j]r-1×[j+1] and \binom[j+1]r×[r]. Consequently, S' 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(klog 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≤ 8 and by an entropy-accounting trace for choosing 20,000 of 30,000 items. We make no claim of runtime superiority over existing subset samplers.