number generator

Paul Rubin http
Tue Mar 13 18:08:36 CET 2007

```"Terry Reedy" <tjreedy at udel.edu> writes:
> 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.

I don't see an efficient way to do that, but will try to look sometime
for the book you cited.

Here is a brute force generation approach (not fully tested since
I'm using Python 2.3):

from itertools import imap

# yield all partitions of n having length k, with many duplications
def _partitions(n,k):
if k==0: return
for i in xrange(1,n-k+1):
for p in partitions(n-i, k-1):
yield (i,)+p

def unique_partitions(n,k):
return sorted(set(tuple(sorted(p)) for p in _partitions(n,k)))

p50_5 = unique_partitions(50,5)
assert len(p50_5) = 2611

Note the use of a generator expression in unique_partitions to
enumerate the non-unique partitions without remembering them all in
memory.  "set" strips out the duplicates and remembers only the unique
ones.  The above takes a few seconds to run on (50,5) on my 1.2 ghz laptop.

```