On Sat, 2007-03-10 at 22:27 -0500, Terry Reedy wrote: > "Anton Vredegoor" <[EMAIL PROTECTED]> wrote in message > news:[EMAIL PROTECTED] > | 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 -- http://mail.python.org/mailman/listinfo/python-list
