
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

Hi Angle, some comment to your code: iterator begin(){ return iterator(items.begin(),0); }; iterator end(){ return iterator(items.end(), items.size()); }; -------------------------- should have const versions too size_type size() { return items.size(); } size_type max_size() { return items.max_size(); } bool empty() { return items.empty(); } -------------------- should all be const "AngleWyrm" <anglewyrm@hotmail.com> wrote in message news:BAY15-DAV12pta7qPsd0001f50d@hotmail.com... |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. your documentation looks very good, though I would like you to consider one important issue: It seems to me that the hat class is more a bunch of algorithms than a container; instead of requiring users to use the hat class, maybe you could see if it is possible to come up with a set of generic algorithms that work on any container with certain properties. br Thorsten

AngleWyrm wrote:
[...] -:|:- AngleWyrm hat container and documentation at http://home.comcast.net/~anglewyrm/hat.html
It might not be a bad idea to use your real name when posting to the Boost list. You might get some more credibility if you do. Dave

"David B. Held" <dheld@codelogicconsulting.com> writes:
AngleWyrm wrote:
[...] -:|:- AngleWyrm hat container and documentation at http://home.comcast.net/~anglewyrm/hat.html
It might not be a bad idea to use your real name when posting to the Boost list. You might get some more credibility if you do.
Seconded. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
participants (4)
-
AngleWyrm
-
David Abrahams
-
David B. Held
-
Thorsten Ottosen