Project Euler # 53 Combinatoric selections in Python

Question

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 = n! / r! (n−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?

from time import time
from math import factorial


def combinations(n, r):
    """Assumes n, r a set of numbers and r number of numbers to choose from n.
    returns number of combinations."""
    return factorial(n) // (factorial(r) * factorial(n - r))


def generate_combinations(n_range, minimum):
    """generates non-distinct combinations in range n_range inclusive that exceed the minimum."""
    for n in range(1, n_range + 1):
        for r in range(1, n):
            combination = combinations(n, r)
            if combination > minimum:
                yield 1


if __name__ == '__main__':
    START_TIME = time()
    print(sum(generate_combinations(100, 10**6)))
    print(f'Time: {time() - START_TIME} seconds.')

Answer 1

This is an expensive way to calculate combinations:

def combinations(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))

Observe that \$\frac{n!}{r!(n-r)!}\$ cancels out to a large degree:

$$ \frac{n · (n-1) ⋯ (n-r+1)}{r!}·\frac{(n-r) ⋯ 1}{(n-r) ⋯ 1} $$ Now, if we expand r!, we get $$ \frac{n · (n-1) ⋯ (n-r+1)}{1 · 2 ⋯ r} $$ Now, n(n-1) must be an exact multiple of 2, and n(n-1)(n-2) must be an exact multiple of 2✕3, etc, so we can compute ⁿCᵣ using relatively small integers (especially if we ensure that r is smaller than n-r by swapping if not):

def combinations(n, r):
    """Return the number of sets of size r which can be drawn from n items
       without replacement."""
    if r > n - r:
        r = n - r
    c = 1
    for d in range(r):
        c = c * (n - d) // (d + 1)
    return c

Surprisingly, this turns out to be slower than the original code using math.factorial() here. But we can make it more readable by using math.comb() directly, for the same performance as the original.

---

It should be clear that if \$^nC_r > k\$, then \$^{n+1}C_r > k\$, and if also \$r+1 <= n-r\$, then \$^nC_{r+1} > k\$. This is something we know just by looking at Pascal's Triangle.

That means that for a given n, if we find the transition value for r, we know instantly how many r to count without testing them all, and have a good starting point for the next n.

That gets us to this function, which effectively traces the boundary of the inequality through Pascal's Triangle:

def generate_combinations(n_range, minimum):
    """Count how many ⁿCᵣ exceed minimum for all n up to n_range, inclusive."""
    r = 1
    for n in range(n_range, 1, -1):
        while math.comb(n, r) <= minimum and r <= n // 2:
            r += 1
        if r > n // 2:        # no qualifying values from n or smaller
            break
        yield n - 2 * r + 1   # count the range r to n-r

On my system, that runs about 100 times faster than the question code, and I expect it to scale better as n_range increases.

Answer 2

just a little hack if you want a more fast solution, can become faster if consider the similarity of the nCr and nC(n-r)

dic=[1]

for i in range(1,101):
    val =dic[-1]*i
    dic.append(val)


def choose(n,r):
    sol = dic[n]//(dic[n-r]*dic[r])
    return sol

def func(maxi, valu): 
    count = 0
    for i in range(2,maxi+1):
        for j in range(1,i+1):
            val = choose(i,j)
            if  val>valu:
                count+=1         
    return count


if __name__ == '__main__':
    from time import time
    START_TIME = time()
    print(func(100, 10**6))
    print(f'Time: {time() - START_TIME} seconds.')

just store all the value of factorial of a number upto 100 in dict and then process

update suggested by @AJNeufeld , using list to store data than dictonary