[boost] C++ random container

From: AngleWyrm (anglewyrm_at_[hidden])
Date: 2004-08-31 22:05:08

A proposal for inclusion into the boost libraries:
-----------------------------------------------

The hat container derives it's name from the act of pulling names from a
hat. It is a container which provides random selection of it's contents,
where the items can have differing probabilities, and can either be removed
like cards from a deck, or come up again like rolling dice.

Rationale
=======

There are easy ways to generate uniform chance containers. If one wishes to
roll a die, it's a simple matter of scaling a random number to the
appropriate range, and then picking from an ordered set. If one wishes to
draw cards from a deck, then it is also easy to place all the cards in a
container and perform a random_shuffle, then take as many as desired from
one end.

In 1977, A.J. Walker published a method for the non-uniform first case, in
"An Efficient Method for Generating Discrete Random Variables with General
Distributions" to the ACM, and Donald Knuth, in his second volume of The Art
Of Computer Programming, "Seminumerical Algorithms" presents an
implementation of Walker's alias algorithm. This alias technique is very
efficient when the probability distribution is fixed before selection, and
answers a large subset of uses. It performs in constant time, once a table
has been set up, which requires linear time.

But there is still one class of problem left out. In the case where the
distribution changes dynamically as choices are added to or removed from the
set, the above technique must recalculate a lookup table for each
insert/delete operation, a linear-time operation. Examples of this problem
space are: Drawing lottery balls, random selection from a changing client
list, or situations where a random sample is taken before all data is
gathered.

The hat container provides a solution for all four of the above scenarios:
uniform and non-uniform distributions, both with and without replacement.
Furthermore, it performs these functions with a time complexity
of O( log n ).

-:|:-
AngleWyrm
hat container and documentation at
http://home.comcast.net/~anglewyrm/hat.html