Combinatorial Selections

Computer Science Level 3

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general,

$nCr=\frac { n! }{ (n-r)!r! }$ .

,where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1. It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?

This problem is from a site known as project euler

The answer is 4075.

3 solutions

Mads I.
Apr 26, 2014

There are two opportunities to avoid a lot of redundant computation here:

Cache the result of factorial computations
If comb(n,r)>c and r<n/2 then comb(n,k)>c for all k in the range r...n-r

This doesn't make much of a difference for maxn=100 though, but going to 10k takes forever without it...

def computeresult(maxn):
    def factable(n):
        fact=range(1,n+1)
        i=1
        while i < n:
            fact[i]=i*fact[i-1]
            i+=1
        return fact

    f=factable(maxn+1)

    def choose(n,k):
        return f[n]/(f[n-k]*f[k])

    result=0;
    for n in range(1,maxn+1):
        for k in range(1,n):
            if choose(n,k) > 1000000:
                result+=2*((n+1)/2-k)+1-n%2
                break

    print maxn
    print result

computeresult(100)

Girish Ramnani
Apr 2, 2014

def combo(n,r):

return (math.factorial(n))/(math.factorial(n-r)*math.factorial(r))

count=0

j=1

for i in range(101):

j=0

while i>j:

    if combo(i,j)>1000000:

        count+=1        

    j+=1

print(count)

dont forget to import math

girish ramnani - 7 years, 2 months ago

Damiann Mangan
Mar 11, 2014

Here's my solution in python,

def comb(a,b):
    x = 1
    for i in xrange(a-b+1, a+1):
        x *= i
    for i in xrange(1, b+1):
        x /= i
    return x > 1000000

foo = 0

for n in xrange(1, 100+1):
    for r in xrange(n+1):
        if comb(n,r):
            foo += 1

print foo

Combinatorial Selections

The answer is 4075.

3 solutions

0 pending reports