Prev: complexity again. (was: on goto)
Next: WTB: I BUY SOFTWARE - CHECK AROUND - YOU PROBABLY HAVE SOME OF THE BELOW TO SELL TO ME.
From: Lie Ryan on 22 May 2010 15:13
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).

Therefore:

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


Now, the method above as is only works when the limit N is a multiple of
10 (e.g. N == {10, 100, 1000, ...}). But it isn't that difficult to
extend it so that it works when N is arbitrary number.




Appendix A:

why does the distribution formula works?

Consider distributing 3 items over 3 buckets:

| |*** = 3
| *| ** = 21
*| | ** = 12
| **| * = 21
*| *| * = 111
**| | * = 201
|***| = 30
*| **| = 120
**| *| = 210
***| | = 300

which can be rewritten as:
||*** = 3
|*|** = 21
*||** = 12
|**|* = 21
*|*|* = 111
**||* = 201
|***| = 30
*|**| = 120
**|*| = 210
***|| = 300

this happens to be the equivalent as the problem of choosing the
Combination of 5 items (3 *s and 2 |s); therefore we can use the
combination formula: C(3 + 2, 3) == C(3 + 3 - 1, 3)

Appendix B:

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

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)


From: superpollo on 22 May 2010 16:14
Lie Ryan ha scritto:
> 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).
>
> Therefore:
>
> I1 - (X1 + X2 + X3) = 153 - (28 * 3) = 69
>
>
> Now, the method above as is only works when the limit N is a multiple of
> 10 (e.g. N == {10, 100, 1000, ...}). But it isn't that difficult to
> extend it so that it works when N is arbitrary number.
>
>
>
>
> Appendix A:
>
> why does the distribution formula works?
>
> Consider distributing 3 items over 3 buckets:
>
> | |*** = 3
> | *| ** = 21
> *| | ** = 12
> | **| * = 21
> *| *| * = 111
> **| | * = 201
> |***| = 30
> *| **| = 120
> **| *| = 210
> ***| | = 300
>
> which can be rewritten as:
> ||*** = 3
> |*|** = 21
> *||** = 12
> |**|* = 21
> *|*|* = 111
> **||* = 201
> |***| = 30
> *|**| = 120
> **|*| = 210
> ***|| = 300
>
> this happens to be the equivalent as the problem of choosing the
> Combination of 5 items (3 *s and 2 |s); therefore we can use the
> combination formula: C(3 + 2, 3) == C(3 + 3 - 1, 3)
>
> Appendix B:
>
> 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
>
> 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)
>
>

i'll print and frame.

thanks
From: Lie Ryan on 24 May 2010 14:14
On 05/23/10 05:13, Lie Ryan wrote:
> 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)
>

more combinatoric magic.

Assuming N == 10**i for some integer i (i.e. N is one of {10, 100, 1000,
10000, ...}).

For example, when calculating prttn(32, 10000) then:

u1 + u2 + u3 + u4 = 32
inclusion (no rule): D(32, 4) * C(4, 0)
exclusion (1 rule): D(22, 4) * C(4, 1)
inclusion (2 rules): D(12, 4) * C(4, 2)
exclusion (3 rules): D( 2, 4) * C(4, 3)
inclusion (4 rules): D(-8, 4) * C(4, 4)

[*] why this works? see Appendix C

>>> D(32, 4) * C(4, 0) - D(22, 4) * C(4, 1) + D(12, 4) * C(4, 2) - D( 2,
4) * C(4, 3) + D( -8, 4) * C(4, 4)
35L
>>> prttn(32, 10000)
35

knowing how to deal when N in {10, 100, 1000, ...}, we have an easy way
to deal when N is a*(10**i)

Appendix B.2:

# memoizing might help a lot here
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

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

Appendix C:

when we apply no rule for inclusion (i.e. uX can range freely between
{0..32}):
u1 + u2 + u3 + u4 = 32
D(32, 4)
{there is C(4, 0) == 1 possibilities}

then when we applying 1 rule for exclusion (i.e. at least one of {0 <=
u1 < 10, 0 <= u4 < 10, 0 <= u4 < 10, 0 <= u4 < 10} is true):
v1 + u2 + u3 + u4 = 22
u1 + v2 + u3 + u4 = 22
u1 + u2 + v3 + u4 = 22
u1 + u2 + u3 + v4 = 22
{there is C(4, 1) == 4 possibilities}

then when we are applying 2 rules for inclusion (i.e. at least two of {0
<= u1 < 10, 0 <= u4 < 10, 0 <= u4 < 10, 0 <= u4 < 10} is true):

v1 + v2 + u3 + u4 = 12
v1 + u2 + v3 + u4 = 12
v1 + u2 + u3 + v4 = 12
u1 + v2 + v3 + u4 = 12
u1 + v2 + u3 + v4 = 12
u1 + u2 + v3 + v4 = 12
{there is C(4, 2) == 6 possibilities}
{note that enumerating this is equivalent to choosing two uX out of four
to be turned into two vX}

then when we are applying 3 rules for inclusion (i.e. at least three of
{0 <= u1 < 10, 0 <= u4 < 10, 0 <= u4 < 10, 0 <= u4 < 10} is true):

v1 + v2 + v3 + u4 = 2
v1 + v2 + u3 + v4 = 2
v1 + u2 + v3 + v4 = 2
u1 + v2 + v3 + v4 = 2
{there is C(4, 3) == 4 possibilities}
{note that enumerating this is equivalent to choosing three uX out of
four to be turned into three vX}

then when we are applying 4 rules for inclusion (i.e. all for of {0 <=
u1 < 10, 0 <= u4 < 10, 0 <= u4 < 10, 0 <= u4 < 10} is true):

v1 + v2 + v3 + v4 = -8
{there is C(4, 4) == 1 possibilities}
{note that D(-8, 4} == 0, so this is only included for algorithm
completeness}
 | 
Pages: 1
Prev: complexity again. (was: on goto)
Next: WTB: I BUY SOFTWARE - CHECK AROUND - YOU PROBABLY HAVE SOME OF THE BELOW TO SELL TO ME.