Project Euler # 53 Combinatoric selections in Python

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.')

• Project Euler problems are typically part coding and part thinking through the constraints of the problem, which can save a lot of compute time. For example, nCr has a consistent shape with a symmetry to it. I would suggest looking at whether you can use that shape to predict which runs of numbers are all high or all low. – Josiah Jul 25 at 7:03
• I assume that you successfully solved PE#53? Did you have a look at the “overview for problem 53” document? 13 pages full of performance tips. – Martin R Jul 25 at 7:37
• @ Martin No not really, can you post a link or something? – user203258 Jul 25 at 7:39
• The link is at the bottom of projecteuler.net/problem=53. It becomes visible as soon as you submit a correct solution. There is also a link to a discussion thread where you can see how other people solved the problem. – Martin R Jul 25 at 7:39
• i'll check it, thanks – user203258 Jul 25 at 7:41

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

• Only the last value of list l is ever used, so this list could be replaced by a scalar variable. Ie) val = 1 outside the for-loop, and val *= i inside the for-loop. Why waste time with a dictionary, when list indexing is way faster? And dic is a meaningless name; how about factorial instead? val = 1; factorial = [1]; for i in range(1, 101): val *= i; factorial.append(val). But this is still the wrong approach if you want speed, which you do since you are going through the effort of timing the code. – AJNeufeld Jul 26 at 5:36
• you are right, using list will do it faster, then adding the dictionary? if this is wrong approach, then how do we speed it more fast ? – temmo Jul 26 at 6:13