Jean-Michel Pichavant wrote: > I still don't see "how many positive integers less than n have digits > that sum up to m" makes it a "partition" though if that what prttn > means. Surely because I miss the context.
A partition of a positive integer m is an unordered collection of positive integers that sum to m. [1, 1, 2, 5] is a partition of 9. The problem at issue here is not that of counting partitions. My algorithm for our prttn separated out the 'ndsums' sub-problem: Count d-digit ints with digits summing to m. I found a generalization of that problem stated in the /CRC Handbook of Discrete and Combinatorial Mathematics/ (2000 edition, section 2.1) among "counting problems" as: Solutions to x_1 + ... x_n = k 0 <= x_i <= a_i for one or more i Alas, the handbook does not provide a formula or algorithm. It refers to the inclusion/exclusion principle, which I did not see how to turn into an efficient algorithm. My recursive memoizing method for ndsums() was initially a shot in the dark and I was surprised how well it worked. Thinking about it more, I can argue that it is polynomial-time based on the size of the memo- table and the work per entry. My prttn() calls ndsums() once for each digit, so the whole thing is polynomial in the number of digits. -- --Bryan -- http://mail.python.org/mailman/listinfo/python-list
