Skip to content

afnanenayet/hashed-permutation

main
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 
src
 
 
 
 
 
 
 
 

hashed-permutation

CI crates badge 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.