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\$ – Emad Boctor 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\$ – Emad Boctor 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\$ – prashant rana Jul 26 at 6:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.