Algorithms for Generating Small Random Samples
Vincent A. Cicirello
Technical Report ALG-24-008, Cicirello.org, May 2024.
Journal Ref
Vincent A. Cicirello. 2025. Algorithms for Generating Small Random Samples. Software: Practice and Experience, February 2025, 55(2): 298-306. https://doi.org/10.1002/spe.3379
Show BibTeX
@article{cicirello2024spe,
title = {Algorithms for Generating Small Random Samples},
author = {Vincent A. Cicirello},
journal = {Software: Practice and Experience},
year = {2025},
volume = {55},
number = {2},
pages = {298--306},
doi = {10.1002/spe.3379},
url = {https://doi.org/10.1002/spe.3379}
}
@techreport{ALG-24-008,
title = {Algorithms for Generating Small Random Samples},
author = {Vincent A. Cicirello},
year = {2024},
month = {May},
number = {ALG-24-008},
institution = {Cicirello.org},
url = {https://reports.cicirello.org/24/008/ALG-24-008.pdf}
}
Abstract
We present algorithms for generating small random samples without replacement. We consider two cases. We present an algorithm for sampling a pair of distinct integers, and an algorithm for sampling a triple of distinct integers. The worst-case runtime of both algorithms is constant, while the worst-case runtimes of common algorithms for the general case of sampling k elements from a set of n increase with n. Java implementations of both algorithms are included in the open source library ρμ.
