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.
More information about the Python-list
mailing list