function that counts...

[Lie Ryan]

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