Boost C++ Libraries: Ticket #920: Proposed extension to random library https://svn.boost.org/trac10/ticket/920 <pre class="wiki">I suggest adding the following utility function to the random library (with perhaps a name change): // PURPOSE: Sample from a set of N values given the // sequence p[1], p[1] + p[2], p[1] + p[2] + p[3], ... // of cumulative probabilities. // // REQUIRE: // - Type Incrementer supports the pre-increment // operation and equality comparison. Typically, // Incrementer will be an integral type or a // forward iterator. // - Pre-incrementing i some finite number of times // -- say, N -- makes it equal to iend. // - cumprob_it "points" at a nondecreasing sequence // of at least N nonnegative numbers, with the N-th // value in the sequence being equal to 1.0. // // RETURNS: // A random value in the interval [i, iend), with // cumprob_it defining the sequence of cumulative // probabilities. template &lt;typename InputIterator, typename Incrementer, class UniformRandomNumberGenerator&gt; Incrementer rand(Incrementer i, Incrementer iend, InputIterator cumprob_it, UniformRandomNumberGenerator &amp; rng) { typedef std::iterator_traits&lt;InputIterator&gt;::value_type number_t; uniform_01&lt;UniformRandomNumberGenerator, number_t&gt; urng(rng); number_t p = urng(); for ( ; p &gt;= *cumprob_it; ++cumprob_t) { ++i; assert(!(i == iend)); } return i; } -- Kevin S. Van Horn (Kevin_VanHorn@ndsu.nodak.edu) </pre> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/920 Trac 1.4.3 nobody Thu, 24 May 2001 03:13:11 GMT <link>https://svn.boost.org/trac10/ticket/920#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/920#comment:1</guid> <description> <pre class="wiki">Logged In: NO These types of sampled probability distributions are very useful. In my field of work they are now more important then the classical functional distributions like Gaussians. The advantage is of course that to arbitary precission they can represent any distribution. I would suggest a common name such as 'parametric_distribution' or 'sampled_distribution' The sort of distribution can be represented in many ways the two major (and interchangable) are as sorted probabilties or as cumulative probabilites. One problem with this concept (a single draw from a distribution) is that it is O(n) where n is parameter table size. However multiple draws can be simplified, by sorting and then searching in the parameter table. At present boot random has no concept for multiple draws. Because of the complexity issue the paramertised_distribution doesn't seem that useful without also a multiple draw concept. In summary either add both or none! </pre> </description> <category>Ticket</category> </item> <item> <dc:creator>Steven Watanabe</dc:creator> <pubDate>Sat, 22 Aug 2009 19:44:50 GMT</pubDate> <title>severity set https://svn.boost.org/trac10/ticket/920#comment:2 https://svn.boost.org/trac10/ticket/920#comment:2 <ul> <li><strong>severity</strong> → <span class="trac-field-new">Showstopper</span> </li> </ul> <p> The new standard will contain a discrete_distribution, which returns an integer given a sequence of weights. </p> Ticket Steven Watanabe Sat, 22 Aug 2009 19:45:33 GMT severity changed https://svn.boost.org/trac10/ticket/920#comment:3 https://svn.boost.org/trac10/ticket/920#comment:3 <ul> <li><strong>severity</strong> <span class="trac-field-old">Showstopper</span> → <span class="trac-field-new">Problem</span> </li> </ul> Ticket Steven Watanabe Mon, 21 Jun 2010 04:07:15 GMT status, resolution changed https://svn.boost.org/trac10/ticket/920#comment:4 https://svn.boost.org/trac10/ticket/920#comment:4 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> <span class="trac-field-old">None</span> → <span class="trac-field-new">fixed</span> </li> </ul> <p> Fixed in <a class="changeset" href="https://svn.boost.org/trac10/changeset/63180" title="Implement discrete_distribution. Fixes #920.">[63180]</a>. </p> Ticket