Is There a Math Ncr Function in Python

Is there a math nCr function in python?

The following program calculates nCr in an efficient manner (compared to calculating factorials etc.)

import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom  # or / in Python 2

---

As of Python 3.8, binomial coefficients are available in the standard library as math.comb:

>>> from math import comb
>>> comb(10,3)
120

Statistics: combinations in Python

See scipy.special.comb (scipy.misc.comb in older versions of scipy). When exact is False, it uses the gammaln function to obtain good precision without taking much time. In the exact case it returns an arbitrary-precision integer, which might take a long time to compute.

Is there a built-in function to calculate nCr in C++?

The beta function from the mathematical library can be used to express binomial coefficients (aka nCr).

double binom(int n, int k) {
    return 1/((n+1)*std::beta(n-k+1,k+1));
}

Source.

This function is available either with C++17 or as part of an implementation of the mathematical special functions extensions for C++ (ISO/IEC 29124:2010). In the latter case, your implementation may require you to #define __STDCPP_WANT_MATH_SPEC_FUNCS__ 1 before including the <cmath> header for the function to be available.

Note that, unlike Python, C++ does not have built-in support for big integer numbers, so using floating point arithmetic is probably a good choice here in the first place.

Python Binomial Coefficient

This question is old but as it comes up high on search results I will point out that scipy has two functions for computing the binomial coefficients:

1. scipy.special.binom()

2. scipy.special.comb()

   import scipy.special
   
   # the two give the same results 
   scipy.special.binom(10, 5)
   # 252.0
   scipy.special.comb(10, 5)
   # 252.0
   
   scipy.special.binom(300, 150)
   # 9.375970277281882e+88
   scipy.special.comb(300, 150)
   # 9.375970277281882e+88
   
   # ...but with `exact == True`
   scipy.special.comb(10, 5, exact=True)
   # 252
   scipy.special.comb(300, 150, exact=True)
   # 393759702772827452793193754439064084879232655700081358920472352712975170021839591675861424
   

Note that scipy.special.comb(exact=True) uses Python integers, and therefore it can handle arbitrarily large results!

Speed-wise, the three versions give somewhat different results:

num = 300

%timeit [[scipy.special.binom(n, k) for k in range(n + 1)] for n in range(num)]
# 52.9 ms ± 107 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit [[scipy.special.comb(n, k) for k in range(n + 1)] for n in range(num)]
# 183 ms ± 814 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)each)

%timeit [[scipy.special.comb(n, k, exact=True) for k in range(n + 1)] for n in range(num)]
# 180 ms ± 649 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

(and for n = 300, the binomial coefficients are too large to be represented correctly using float64 numbers, as shown above).

How do you replace factorial, nCr and nPr operations in python?

Here is what you can do:

import re

input_line = "2*x + (9-5)! + 99! + max! + (x-3)! -4"

pattern = "\(.+?\)(?=!)|[0-9]+(?=!)|[a-z]+(?=!)"
result = re.findall(pattern, input_line)
print(result)
output_line = input_line
for match in result:
    if match[0] == '(':
        output_line = output_line.replace(f"{match}!", f"math.factorial{match}")
    else:
        output_line = output_line.replace(f"{match}!", f"math.factorial({match})")

print(output_line)

It first creates a regular expression "\(.*?\)(?=!)| [0-9]*(?=!)| [a-z]*(?=!)"
which is then matched against the input line. All matches are stored in result.

You then replace all matches in the input line with the desired part.
Running this will produce the output:

2*x + math.factorial(9-5) + math.factorial(99) + math.factorial(max) + math.factorial(x-3) -4

You can do it a similar way for other operators.

EDIT: I could not stop myself from trying more.
This gets closer to a good solution, but still has flaws.

import re

input_line = "2*x + (9-5)! + 99! + max! + (x-3)! -4 * ((7 + 2!)!)"
pattern_1 = "[0-9]+(?=!)"
pattern_2 = "[a-z]+(?=!)"
pattern_3 = "\(.+?\)(?=!)"
result_1 = re.findall(pattern_1, input_line)

output_line = input_line
result_3 = re.findall(pattern_3, output_line)

for match in result_3:
    output_line = output_line.replace(f"{match}!", f"math.factorial{match}")
for match in result_1:
    output_line = output_line.replace(f"{match}!", f"math.factorial({match})")
result_2 = re.findall(pattern_2, input_line)
for match in result_2:
    output_line = output_line.replace(f"{match}!", f"math.factorial({match})")
result_3 = re.findall(pattern_3, output_line)

print(output_line)

It creates the output:

2*x + math.factorial(9-5) + math.factorial(99) + math.factorial(max) + math.factorial(x-3) -4 * math.factorial((7 + math.factorial(2)))

Get a number of possible combinations Python

So, you actually need a way to count the Binomial coefficient, right?

import math

def binomial_cooefficient(n: int, k: int) -> int:
    n_fac = math.factorial(n)
    k_fac = math.factorial(k)
    n_minus_k_fac = math.factorial(n - k)
    return n_fac/(k_fac*n_minus_k_fac)

This might not be the most optimal implementation, but it works :)

How to avoid redundant steps in calculation of number of permutations?

You can use scipy.special.comb for this. Switching exact to True gives the exact answer as an integer at the cost of speed.

>>> from scipy.special import comb
>>> comb(10, 5, exact=False, repetition=False)
252.0
>>> comb(10, 5, exact=True, repetition=False)
252

counting combinations and permutations efficiently

if n is not far from r then using the recursive definition of combination is probably better, since xC0 == 1 you will only have a few iterations:

The relevant recursive definition here is:

nCr = (n-1)C(r-1) * n/r

This can be nicely computed using tail recursion with the following list:

[(n - r, 0), (n - r + 1, 1), (n - r + 2, 2), ..., (n - 1, r - 1), (n, r)]

which is of course easily generated in Python (we omit the first entry since nC0 = 1) by izip(xrange(n - r + 1, n+1), xrange(1, r+1)) Note that this assumes r <= n you need to check for that and swap them if they are not. Also to optimize use if r < n/2 then r = n - r.

Now we simply need to apply the recursion step using tail recursion with reduce. We start with 1 since nC0 is 1 and then multiply the current value with the next entry from the list as below.

from itertools import izip

reduce(lambda x, y: x * y[0] / y[1], izip(xrange(n - r + 1, n+1), xrange(1, r+1)), 1)

---

Related Topics