Lie Ryan wrote: > 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
It doesn't seem to work. I get no answer at all, because it recursion- loops out when it calls fact() with a negative integer. -- --Bryan -- http://mail.python.org/mailman/listinfo/python-list