number generator

Carsten Haese carsten at uniqsys.com
Mon Mar 12 14:41:17 CET 2007


On Sat, 2007-03-10 at 22:27 -0500, Terry Reedy wrote:
> "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 [...]
> | [...] 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.

Correct, the OP's spec doesn't allow 0s, but the problem can be easily
transformed back and forth between positive partitions and non-negative
partitions. In order to partition M into N positive numbers, partition
(M-N) into N non-negative numbers and increase each part by 1.

There must be some other constraint on what P(M,N) means, or I just
solved a 300 year old problem.

-Carsten





More information about the Python-list mailing list