Permutation and Combination using Python

Permutation in mathematics is defined as the number of arrangement of its member in a set. It is the number of possible arrangement in total number of member in a set, “n” while taking a number of member, “r” each time.

Combination in mathematics is defined as the number of arrangement in a set without the selection order. It is very similar to permutations, the only differnce being the order of selection is not taken into account.

The general formula of permutation is

The general formula of combination is

where n is the total number of subject in a set and r is the number of subject taken each time.

Here are a few methods that can be used in solving both using Python.

1. Raw mathematics
2. Factorial
3. Stirling’s Approximation
4. Using lists

1. Raw mathematics

This method is straight forward where we solve the equation by splitting the equation into numerator and denominator using for loops. However, this method is a linear method which makes it computational expensive when dealing with a large “n” number.

2. Factorial

This method is similar to the previous method and the only differences is by using the factorial function of the math library.

3. Stirling’s Approximation

This method as the name said uses Stirling’s approximation, an approximation for factorial. The formula of this approximation is

Stirling’s Approximation used in my code

It is useful to compute for larger “n” number and less computational expensive compared to the previous methods. The drawback of this method is mainly due to the fact that it is an approximation and the output contains decimals.

4. Using lists

Permutation and combination involve multiplications of series of numbers. Using list and filtering out the elements by comparing the numerator of denominator of the general formula. The computational costs of this method sits between the approximation and raw maths/factorial as it removes some of the elements before the multiplications.

The implementation of these methods can be found at https://github.com/ChuinHongYap/math-python.

I am Chuin Hong Yap, a PhD candidate in Computer Science and a lifelong learner. You can find me on Twitter at ChuinHongYap.

If you enjoyed this article, please feel free to recommend and share it! Thanks for reading.