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
| > equi-probable random count in the range can be turned into a 
equi-probable
| > 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 Python-list mailing list