#permutation #hashed #instant #permute #performance

hashed-permutation

A fast, instant-access way to permute a range of numbers

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

#1169 in Algorithms

MIT license

17KB
204 lines

hashed-permutation

Build Status Documentation License

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

~0.3–0.8MB
~19K SLoC