number generator

[Terry Reedy]

"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 equi-probable, 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 
equi-probable random count in the range can be turned into a equi-probable 
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