number generator
Terry Reedy
tjreedy at udel.edu
Sat Mar 10 21:59:35 CET 2007
"Anton Vredegoor" <anton.vredegoor at gmail.com> wrote in message
news:esukru$1v1$1 at news2.zwoll1.ov.home.nl...
 Raymond Hettinger wrote:

 > To make the solutions equiprobable, a simple approach is to
 > recursively enumerate all possibilities and then choose one of them
 > with random.choice().

 Maybe it is possible to generate the possibilities by an indexing
 function and then use randint to pick one of them. I suppose this is
 like the bricks and bins problem this thread was about:


http://groups.google.nl/group/comp.lang.python/browse_thread/thread/4782b54fa39b3bad

 Except that the bins now have at least 1 brick in them (if we have
 positive numbers).

 I posted a rather simplistic solution (but working I think) after Steven
 Taschuk made some insightful remarks. I believe it is possible to
 generate the list of numbers directly instead of permuting a list of '0'
 and '1' characters and then finding the positions of the '1' elements.
Partitioning positive count m into n positive counts that sum to m is a
standard combinatorial problem at least 300 years old. The number of such
partitions, P(m,n) has no known exact formula but can be computed
inductively rather easily. The partitions for m and n can be ranked in
lexicographic order from 0 to P(m,n)1. Given a rank r in that range, one
can calculate the particular partition that has that rank. So a
equiprobable random count in the range can be turned into a equiprobable
random partition.
This topic is section 3.1 in Combinatorial Algorithms: Generation,
Enumeration, and Search by Kreher and Stinson. The authors reference
several other books as their sources.
I plan to someday rewrite many of their pseudocode algorithms in Python.
Terry Jan Reedy
More information about the Pythonlist
mailing list