Prev: KOBWEB JAVA
Next: WinMenus version 1.0 ...
From: superpollo on 19 May 2010 16:00
in python:

def prttn(m, n):
tot = 0
for i in range(n):
s = str(i)
sum = 0
for j in range(len(s)):
sum += int(s[j])
if sum == m:
tot += 1
return tot

any suggestion for improvement?

bye
From: Kai-Uwe Bux on 22 May 2010 20:53
Lie Ryan wrote:

> On 05/20/10 06:00, superpollo wrote:
>> in python:
>>
>> def prttn(m, n):
>> tot = 0
>> for i in range(n):
>> s = str(i)
>> sum = 0
>> for j in range(len(s)):
>> sum += int(s[j])
>> if sum == m:
>> tot += 1
>> return tot
>>
>> any suggestion for improvement?
>>
>> bye
>
> This is a partitioning/distribution problem.
>
> Given:
> u1 + u2 + u3 + ... + uN = M
> with restrictions 0 <= uX <= 9 for all X in {1..N}
>
> You can solve this problem with some combinatorics magic.
>
>
>
> Let C(n, r) be Combination function (i.e. (n!) / ((n-r)!(r)!)) then
>
> The number of possible ways to Partition/Distribute M items over N
> buckets is given by:
>
> D(M, N) = C(M + N - 1, M)
>
> [*] for why the formula works, see below
>
>
> Using the same example as Kai-Uwe Bux, if we want to solve how many 3
> digit number (i.e. < 1000) have digits that add up to 16, we can have:
>
> u1 + u2 + u3 = 16 ; 0 <= uX <= 9 for all X in {1, 2, 3}
>
> that means
>
> M = 16
> N = 3 // there are u1,u2,u3 so 3 buckets
> I1: D(16, 3) = C(16 + 3 - 1, 16) = 153
>
> Therefore, there are 153 ways to distribute 16 items over 3 bucket.
> However, we have not put any restrictions on uX,
> the calculations we did includes cases where the "digits" can be greater
> than 9, e.g. u1 = 14
>
> so we need to exclude the cases where u1 >= 10.
>
> let v1 = u1 + 10
>
> u1 + u2 + u3 = 16
> v1 + 10 + u2 + u3 = 16
> v1 + u2 + u3 = 6
>
> now we need to distribute 6 items over another 3 buckets (v1, u2, u3),
> using the distribution formula:
>
> X1: D(6, 3) = C(6 + 3 - 1, 6) = 28
>
> also, we need to exclude the cases where u2 >= 10 and u3 >= 10
> by using similar argument as when u1 >= 10:
>
> X2: D(6, 3) = 28
> X3: D(6, 3) = 28
>
> in this particular case, we couldn't have double-excluded anything so we
> don't need to include any more things using Principle of
> Inclusion-Exclusion (read on this later, it's an important principle on
> how the counting works).

I like that. Here is an alternative account that does not overcount and
hence does not use inclusion exclusion.

The idea is as follows: first, choose the positions of the 9s. You can put,
k = 0, 1, ... m/9 of them. For each value k, you have (n choose k)
placements and in the remaining n-k slots, you get to put the digits
0,1,...,8 with total sum m - k*9. That suggests a recursion:

N(m,n,b) := number of n-digit strings in base b with digit sum m.

N(m,n,b) = ( n choose m ) if b = 2
N(m,n,b) = sum_{k=0}^{m/(b-1)} ( n choose k ) * N( m-(b-1)*k, n-k, b-1 )


> Therefore:
>
> I1 - (X1 + X2 + X3) = 153 - (28 * 3) = 69
>

Admittedly, N(m,n,b) involves more terms even for this example, but is very
easy to implement and still a vast improvement over checking each candidate.
I have to think about inclusion/exclusion a bit more.

[...]


Best

Kai-Uwe Bux
 | 
Pages: 1
Prev: KOBWEB JAVA
Next: WinMenus version 1.0 ...