rdeck: a unique algorithm for randomly selecting distinct values

Usage

most common usecases should be covered by calling to_deck on a range or slice.

once you have the deck, simply call deck.draw() as many times as you wish (or try_draw() if there is a chance you will run out of elements in the deck).

Why

say you are trying to select two random integers, and you want them to be:

1. distinct
2. uniformly distributed
3. generated in constant time

there are a number of trivial solutions, but all of them have problems:

• increment one if they are equal (breaks #2)
• call rng again if they are equal (breaks #3)
• generate a list, pick randomly from that list, removed the picked item, pick randomly again (breaks #3)

How

the basic principle is instead of having a list of items that haven't been selected, you have a list of items that have been selected.

this means the memory and cpu complexity are proportional to the number of elements being selected instead of the number of potential elements.

it also makes it trivial to reset the deck to its original state.

in practice, only IntDeck does this, and everything else is simply built on top of IntDeck.