Velocity Reviews > Re: function that counts...

# Re: function that counts...

Jean-Michel Pichavant
Guest
Posts: n/a

 05-24-2010
Jerry Hill wrote:
> On Wed, May 19, 2010 at 3:58 PM, superpollo <(E-Mail Removed)> wrote:
>
>> ... how many positive integers less than n have digits that sum up to m:
>>

> ...
>
>> any suggestion for pythonizin' it?
>>

>
> This is how I would do it:
>
> def prttn(m, n):
> """How many positive integers less than n have digits that sum up to m"""
> total = 0
> for testval in range(n):
> sumofdigits = sum(int(char) for char in str(testval))
> if sumofdigits == m:
> total += 1
>
> I added a docstring to the function, saying what it does, and what the
> arguments are supposed to represent. I also moved the
> convert-to-string-and-sum-the-digits logic into a single generator
> expression that's passed to the builtin sum function. Oh, and I tried
> to use slightly more expressive variable names.
>
>

my favorite solutio nso far.

@ OP

What means prttn ? is it any Dutch word ? m & n are also very poors
argument names.
I will be difficult to name properly the function, as it is doing
something ... I don't find the word, something like un-intuitive. Sounds
like homework.

def how_many_positive_integers_less_than_n_have_digits _that_sum_up_to_m(m, n)

)

JM

<http://tottinge.blogsome.com/meaningfulnames/>

Jean-Michel Pichavant
Guest
Posts: n/a

 05-25-2010
superpollo wrote:
> Jean-Michel Pichavant ha scritto:
>> Jerry Hill wrote:
>>> On Wed, May 19, 2010 at 3:58 PM, superpollo <(E-Mail Removed)> wrote:
>>>
>>>> ... how many positive integers less than n have digits that sum up
>>>> to m:
>>>>
>>> ...
>>>
>>>> any suggestion for pythonizin' it?
>>>>
>>>
>>> This is how I would do it:
>>>
>>> def prttn(m, n):
>>> """How many positive integers less than n have digits that sum
>>> up to m"""
>>> total = 0
>>> for testval in range(n):
>>> sumofdigits = sum(int(char) for char in str(testval))
>>> if sumofdigits == m:
>>> total += 1
>>>
>>> I added a docstring to the function, saying what it does, and what the
>>> arguments are supposed to represent. I also moved the
>>> convert-to-string-and-sum-the-digits logic into a single generator
>>> expression that's passed to the builtin sum function. Oh, and I tried
>>> to use slightly more expressive variable names.
>>>
>>>

>> my favorite solutio nso far.
>>
>> @ OP
>>
>> What means prttn ?

>
>
>> something ... I don't find the word, something like un-intuitive.
>> Sounds like homework.

>
> it is not.

My apologies then, for both statements.
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.

JM

Bryan
Guest
Posts: n/a

 05-26-2010
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.

My recursive memoizing method for ndsums() was initially a shot in the
dark and I was surprised how well it worked. Thinking about it more, I
can argue that it is polynomial-time based on the size of the memo-
table and the work per entry. My prttn() calls ndsums() once for each
digit, so the whole thing is polynomial in the number of digits.

--
--Bryan

Bryan
Guest
Posts: n/a

 05-26-2010
I wrote:
> My prttn() calls ndsums() once for each
> digit, so the whole thing is polynomial in the number of digits.

Correction: my prttn() function calls ndsums() at most 9 times per
digit of n. That still provides run time polynomial in the length of
the input.

--
--Bryan

Lie Ryan
Guest
Posts: n/a

 05-29-2010
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
)

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

Bryan
Guest
Posts: n/a

 06-09-2010
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

Lie Ryan
Guest
Posts: n/a

 06-10-2010
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.

Bryan
Guest
Posts: n/a

 06-11-2010
Lie Ryan wrote:
> 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

Ah, much better, but partition10(M, i) gets the wrong answer when i is
1 or 2. I think you don't want to let M go negative. With that tweak,
it seems to work in general, and fact() never gets called with a
negative number.

efficiently handle bases much larger than 10. Richard Thomas's
algorithm is poly-time and efficient as long as the base is small.

I'll take the liberty of tweaking your code to handle the 1 or 2 digit
case, and write the more general form. I'll also memoize fact(), and

--
--Bryan

_ft = [1]
def fact(n):
assert n >= 0 and n % 1 == 0
if len(_ft) <= n:
for i in range(len(_ft), n + 1):
_ft.append(i * _ft[-1])
return _ft[n]

def C(n, r):
""" regular Combination (nCr) """
return fact(n) // (fact(n - r) * fact(r))

def D(M, N):
""" Distribution aka Partitioning """
assert M >= 0 and N > 0
return C(M + N - 1, M)

def partition(nballs, nbins, binmax):
"""Count ways to put identical balls into distinct bounded bins.
"""
if nbins == 0:
return int(nballs == 0)
s = 0
sign = 1
for j in range(1 + min(nbins, nballs // binmax)):
s += sign * D(nballs, nbins) * C(nbins, j)

# flip the sign for inclusion-exclusion
sign *= -1
nballs -= binmax
return s

def prttn(m, n):
assert m >= 0 and n > 0
count = 0
dls = [int(c) for c in reversed(str(n))]
while dls:
msd = dls.pop()
count += sum(partition(m - d, len(dls), 10) for
d in range(min(msd, m + 1)))
m -= msd
return count

def test():
upto = 123456
counts = [0] * (len(str(upto)) * 9)
for n in range(upto):
digits = [int(c) for c in str(n)]
counts[sum(digits)] += 1
for m in range(9 * len(digits) + 2):
count = prttn(m, n + 1)
assert count == counts[m]
if count == 0:
break
assert count == 0
if n % 1000 == 0:
print('Tested to:', n)

test()