number generator
Terry Reedy
tjreedy at udel.edu
Sun Mar 11 04:27:56 CET 2007
"Anton Vredegoor" <anton.vredegoor at gmail.com> wrote in message
news:esvepk$1cu$1 at news3.zwoll1.ov.home.nl...
 Terry Reedy wrote:

 > 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
 > equiprobable random count in the range can be turned into a
equiprobable
 > random partition.

 Yes that was one of my first ideas too. But later on Steven pointed out
 that one can view the problem like this:

 00010000100010100

 That would be [3,4,3,1,2]

 where the '1' elements are like dividing shutters that partition the row
 of '0'. This means that the problem is reduced to permutations (albeit
If any of the 1s appear at the ends or together, then you would have 0s in
the partition, which is not allowed, as I understood the spec.
 unique permutations) which are a lot simpler to compute than partitions.
I think the simplicity is actually about the same.
Terry Jan Reedy
More information about the Pythonlist
mailing list