Combination and permutation calculations appear often in daily programming challenges such as HackerRank. Even though we all know how to calculate these values from high school day, this becomes challenging when we are working on really large numbers. We can apply some hacking skills to the traditional formulas and transform these calculations in a simpler form. Let’s do cracking the coding interview!
Vlog
You can either watch the following vlog or follow this blog post.
Combination
Traditional formula of r-combination (or n choose r) is:
C(n, r) = n! / (r! . (n-r)!)
For example, 5 choose 3 will be:
C(5,3 ) = 5! / (3! . (5-3)!) = 5! / (3! . 2!) = 120 / (6 . 2) = 10
Adapting combination in python programming languages is easy.
n = 5 r = 3 comb = math.factorial(n) / (math.factorial(r) * math.factorial(n-r))
However, this approach will cause trobule for large integers.
n = 5000000; r = 10000
Even though you can find the factorial values, you will have “integer division result too large for a float” message. Handling this exception is easy. Replacing division operator from single division sign to double division sign will solve this.
comb = math.factorial(n) // (math.factorial(r) * math.factorial(n-r))
However, you will still have performance issues. Because, you have to perform factorial calculations of 3 different large numbers. 5M choose 10K did last 363.25 seconds (or 6 minutes).
Wide your viewpoint
On the other hand, we can speed it up if we wide our viewpoint. Let’s focus on the C(5, 3) again.
C(5, 3) = 5! / (3! . (5-3)!) = 5! / (3! . 2!)
The maximum one in the divisor is 3!. Express dividend as the greater one in the dividend.
C(5, 3) = (5.4.3!) / (3! . 2!)
We can now simplify the 3! terms in both dividend and divisor.
C(5, 3) = (5.4) / (2!)
So, we do not need to calculate the factorial of 3 anymore. Imagine this for a large n and r pair. We firstly applied by-pass for a factorial calculation. Besides, we will calculate small sized multiplications in dividend instead of a large factorial calculation.
dividend = 1 if r > (n - r): a = r b = (n - r) else: a = (n-r) b = r for i in range(n, a, -1): dividend = dividend * i fast_combination = dividend // math.factorial(b) print(fast_combination)
Calculation of 5M choose 10K completed in 0.077 seconds in this way. This is 4705 times faster than the traditional approach.
Permutation
Similarly, we can calculate the permutation faster in this way.
P(n, r) = n! / (n-r)!
We can adapt permutation in python easily.
#permutation = math.factorial(n) // math.factorial(n-r) #traditional permutation fast_permutation = 1 for i in range(n, (n-r), -1): fast_permutation = permutation * i
Faster way completed in 0.1218 seconds for P(5M, 10K) whereas traditional method completed in 708.82 seconds (11 minutes). In other words, this approach is 5818 times faster than the traditional approach.
So, we’ve mentioned how to find permutation combination pair in a faster way. Even a little touch to the formula speeds the calculation radically. We just wide our viewpoint. This show the importance of hacking skills in daily problems.
Support this blog if you do like!
