This notebook is inspired by an old website from UC Berkley on Hamiltonian paths. The code examples described here are updated to Python 3.
In mathematics, the factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to n.
For example:
Using python 3 reduce function, the $n!$ can be computed efficiently.
In [1]:
from functools import reduce
In [2]:
k=5
reduce(lambda i,j : i*j, range(1,k+1))
Out[2]:
Let us consider a small thought experiment involving picking types of fruits. For example, given three fruits, say an apple, an orange and a pear. We are allowed to pick two fruits from this basket. The possible outcome for choices can be computed by simply listing all the combinations. Here, there will be three combinations of two fruits that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange.
But, when the problem of selecting items involves a much larger sample size, it becomes impractial to write down a complete list of combinations. A great example for this is a poker hand. It can be described as a 5-combination $(k = 5)$ of cards from a 52 card deck $(n = 52)$. The 5 cards of the hand are all distinct, and the order of cards in the hand does not matter. There are 2,598,960 such combinations, and the chance of drawing any one hand at random is $\frac{1}{2,598,960}$.
One important concept to note here is that the set from where we are picking the elements from are all unique.
Mathematically, a k-combination of a set S is a subset of $k$ distinct elements of S. If the set has $n$ distinct elements, the number of k-combinations is equal to the binomial coefficient.
It can be expressed as:
${\binom {n}{k}} = \frac {n(n-1)...(n-k+1)} {k(k-1)...1}$
Alternatively, the formula above can be expressed using fatorials as:
${\binom {n}{k}} = \frac {n!} {k!(n-k!)}$
The expression: ${\binom {n}{k}}$ is often read as "$n$ choose $k$".
One of the challenges of designing a python function that computes combination is the efficiency of the computations involved and the ability to handle the unusal scenarios where the formula above can involve division by $0$ or $\frac {\infty}{\infty}$.
If the sample sizes of $n$ (the set from which the distinct elements are drawn from) and $k$ (the set that receives the selected items) satisfy the condition, $n=k$, then there is only one possible outcome combination available.
If $n$ and $k$ satisfy the condition, $n>0$ and $k=0$ or when $n=k$ then there is only one possible combination available.
If $n$ and $k$ satisfy the condition, $n>0$ and $n<k$ then the result will be zero.
If $n$ and $k$ satisfy the condition, $n=0$ and $k=0$, then the number of possible outcome combinations are undefined, due to $\frac{0}{0}$.
In [3]:
def combination(n,k):
"""
This function computes the combination of two integers, n and c, given by the formula using factorials:
n!
-------
k! (n-k)!
Params: n, k -- Both should be non-negative, integers.
"""
if not isinstance(n, int) or not isinstance(k, int):
raise ValueError("To compute combination of n and k, both n and k must be non-negative integers.")
elif n==0 and k==0:
raise ValueError("To compute combination of n and k, both n and k cannot be zero. Result is zero divided by zero, which is undefined.")
elif n==k:
return 1
elif k==0:
return 1
elif n<k:
return 0
elif n>0 and k>0 and n>k:
return int((reduce(lambda i,j : i*j, range(1,n+1)))/((reduce(lambda i,j : i*j, range(1,k+1)))*(reduce(lambda i,j : i*j, range(1,n-k+1)))))
else:
raise ValueError("To compute combination of n and k, both n and k must be non-negative integers.")
In [4]:
print (combination(52,5))
In [5]:
print (combination(52,0))
In [6]:
print (combination(52,52))
In [7]:
print (combination(52,56))
In [8]:
print (combination(0,0))
In [9]:
print (combination(52,0))
In [10]:
print (combination(52,2.5))
In [ ]: