8 stable releases
3.0.2 | Dec 26, 2020 |
---|---|
3.0.1 | May 10, 2020 |
2.2.0 | May 10, 2020 |
2.1.1 | Sep 11, 2019 |
1.0.0 | Sep 9, 2019 |
#1148 in Algorithms
17KB
204 lines
hashed-permutation
Synopsis
This is an implementation of Andrew Kensler's hashed permutation, which allows you to take an array of the elements [0 ... n) and shuffle it with no memory overhead and very little computational overhead. This works by using a clever hash function to effectively permute all of the elements in the array.
Basically, you get a nearly free method to shuffle a bunch of numbers that
doesn't require you to allocate a vector of size n
, letting you sample the
set without replacement.
You can find the paper here: https://graphics.pixar.com/library/MultiJitteredSampling/paper.pdf. I have a little writeup of how the algorithm works here, and Timothy Hobbs made a nice writeup explaining how to use the library itself here.
Dependencies
~270–800KB
~18K SLoC