On 06/10/10 09:03, Bryan wrote:
> 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.
Why of course you're right! In my original post in comp.programming, I
used this definition of factorial:
def fact(n):
""" factorial function (i.e. n! = n * (n-1) * ... * 2 * 1) """
p = 1
for i in range(1,n+1):
p *= i
return p
when I reposted it here, I substituted that factorial to the recursive
definition which fails when n is negative without much testing and that
causes things to fails miserably. Sorry about that.
--
http://mail.python.org/mailman/listinfo/python-list
