# 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 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:
|
|
|
| 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

```