number generator

[Paul Rubin]

"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.