Combinatorics: (n choose r)

Here is a quick function to calculate (n choose r) i.e. in how many ways you can combine “r” items out of total of “n” items.

def nCr(n,r):
	print(f"n,r: {n}, {r}")
	assert n >= r, "nCr : n < r !"
	r = min(r,n-r)
	if r == 0 : return 1
	numerator = reduce(op.mul, range(n,n-r,-1))
	denominator = reduce(op.mul, range(1, r+1) )
	return numerator//denominator

and here is in JavaScript :

N :
R :
(N R) :
calculate

This uses several interesting tricks which I should probably explain in a separate post : generators, range, splat operator.

function* range(start, end, step) {
	step = step || 1
	if (step > 0) { for (let i = start; i < end; i+= step) yield i; }
	else { for (let i = start; i > end; i+= step) yield i;}
}

Math.mul = (a,b) => a * b
  
function nCr(n,r) {
        if (r > n) return 'r > n ??'
	r = Math.min(r,n-r)
	if (r == 0) return 1
	numerator = [...range(n,n-r,-1)].reduce(Math.mul)
	denominator = [...range(1, r+1)].reduce(Math.mul)
	return Math.floor(numerator/denominator)
}

Tags: combinationsmulti-language