function that counts...

[superpollo]

Richard Thomas ha scritto:
> For this kind of problem you should avoid all that stringification. I
> find it best to deal with sequences of digits of a fixed length and go
> from there. For example:
> 
> def count1(m, n, cache={}):
>     """Number of digit sequences of length `n` summing to `m`."""
>     if n < 0 or m < 0:
>         return 0
>     elif n == 0:
>         return int(m == 0)
>     elif (m, n) in cache:
>         return cache[m, n]
>     # This is an optimisation using the combinatoric choose function.
>     #elif m < 10:
>     #    result = choose(n + m - 1, n - 1)
>     else:
>         result = 0
>         for digit in xrange(min(10, m + 1)):
>             result += count1(m - digit, n - 1)
>     cache[m, n] = result
>     return result
> 
> Notice the caching of results. With this we can compute the required
> thing quite easily:
> 
> def count2(m, n):
>     """Number of numbers less than `n` whose digits sum to `m`."""
>     result = 0
>     digits = map(int, str(n))
>     length = len(digits)
>     for idx, digit in enumerate(digits):
>         for seq_digit in xrange(digit):
>             seq_limit = m - seq_digit
>             seq_length = length - idx - 1
>             result += count1(seq_limit, seq_length)
>         m -= digit
>     return result
> 
> Essentially we move through the number left to right, choose digits
> less than the digit in the number and count digit sequences to fill
> the remainder. Then fix the actual digit and step forward.
> 
> An approach like this avoids the relatively slow stringification
> process and makes decent use of caching and iteration (both easy and
> efficient in Python).
> 
> In [1]: count2(25, 10000)
> Out[1]: 348
> 
> In [2]: timeit count2(25, 10000)
> 100000 loops, best of 3: 12.6 us per loop

wow.

impressive, thanks.