On 05/26/10 11:04, Bryan wrote: > 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.
superpollo posted this question in comp.programming (http://groups.google.com/group/comp.programming/browse_thread/thread/e3b10346db8ebd0a/579ca67f8b9b5a8c; http://groups.google.com/group/comp.programming/msg/f7323d6e6942e883; http://groups.google.com/group/comp.programming/browse_thread/thread/e3b10346db8ebd0a/dc4cd1e2feb89500 ) I went through the mathematical foundation of using partition/distribution and inclusion-exclusion, and have written some code that solves a subset of the problem, feel free if you or superpollo are interested in continuing my answer (I won't be able to continue it until next week, have been a little bit busy here) copying the code here for convenience: # memoization would be very useful here def fact(n): """ factorial function (i.e. n! = n * (n-1) * ... * 2 * 1) """ return n * fact(n - 1) if n != 0 else 1 def C(n, r): """ regular Combination (nCr) """ return fact(n) / (fact(n - r) * fact(r)) def D(M, N): """ Distribution aka Partitioning """ return C(M + N - 1, M) def partition10(M, i): """ Count how many integer < N sums to M where N = 10**int(i) """ s = 0 sign = 1 for j in range(i + 1): s += sign * D(M, i) * C(i, j) # flip the sign for inclusion-exclusion sign *= -1 # if M = 32, then 32, 22, 12, 2, -8 M -= 10 return s # still need to write: # def partitionN10(...): -- applies a "restriction"/"boundary" to # the most significant digit # then make it recurse. # assuming factorials calculation is constant time (hint: memoization) # the resulting code should work in O(n**2) # an improvement over the naive method which is O(10**n) # where n is the number of digits in N # DISCLAIMER: the big-O is a quick guess, not really calculated -- http://mail.python.org/mailman/listinfo/python-list
