simulate binominal coefficent (nCr) in python

Question

Out of curiosity, I was wondering if there's a way to solve a binominal coefficient by simulation in python. I tried a little bit, but the numbers are getting so big so quickly that I wasn't able to solve it for anything but really small numbers.

I'm aware of this question but wasn't able to identify one solution that uses only brute force to solve the coefficient. But I have to admit that I don't understand all the implementations listed there.

Here's my naive approach:

import random
import numpy as np
from math import factorial as fac

# Calculating the reference with help of factorials

def comb(n,k):
    return fac(n) // fac(k) // fac(n-k)

# trying a simple simulation with help of random.sample

random.seed(42)
n,k = 30,3
n_sim = 100000
samples = np.empty([n_sim,k], dtype=int)


for i in range(n_sim):
    x = random.sample(range(n),k)
    samples[i] = sorted(x)

u = np.unique(samples, axis=0)

print(len(u))
print(comb(n,k))

Would it be possible to do this efficiently and fast for big numbers?

I don't get your code : 8 lines to built "u", which is not used... plus : function comb as defined in your code is fast on my computer and can handle quite big numbers, even if it is quite a vague definition... — Setop, Dec 18 '17 at 10:37

score 0 · Answer 1 · answered Dec 18 '17 at 10:33

0

I use this, its pretty efficient for large numbers:

def nck(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    k = min(k, n - k)  # take advantage of symmetry
    c = 1
    for i in range(k):
        c = c * (n - i) // (i + 1)
    return c

answered Dec 18 '17 at 10:33

Christian Sloper

7,440
3
15
28

it may be magic, but using timeit, it shows to be two to three times slower than using `fac` – Setop Dec 18 '17 at 13:32
Not for big numbers it isnt. try: `nck(10**6,50*10**3)` vs `comb(10**6,50*10**3)` (4s vs 46s on my computer) – Christian Sloper Dec 18 '17 at 14:13

simulate binominal coefficent (nCr) in python

1 Answers1