Exact Online Rank Recycling in Floyd's Uniform Subset Sampler

Yingqi Zhang

A uniformly random $m$-subset of $[n]=\{0,\dots ,n-1\}$ has entropy ${\log }_2\left(\genfrac{}{}{0ex}{}{n}{m}\right)$. Standard without-replacement procedures often expose an additional ordering coordinate tha…