function that counts...

[Lie Ryan]

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.