3
\$\begingroup\$

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.')
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Josiah Jul 25 at 7:03
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin R Jul 25 at 7:37
  • \$\begingroup\$ @ Martin No not really, can you post a link or something? \$\endgroup\$ – user203258 Jul 25 at 7:39
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin R Jul 25 at 7:39
  • \$\begingroup\$ i'll check it, thanks \$\endgroup\$ – user203258 Jul 25 at 7:41
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – AJNeufeld Jul 26 at 5:36
  • \$\begingroup\$ 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 ? \$\endgroup\$ – temmo Jul 26 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy