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