added combination_memo.py using memoization (keon#358)

* Update combination.py * Update test_maths.py * fixed test_maths.py * update function combination_memo * update test of combination_memo
vdsmitnov52 · Jun 18, 2018 · 37bee74 · 37bee74
1 parent 7cbe6e1
commit 37bee74
Show file tree

Hide file tree

Showing 2 changed files with 16 additions and 3 deletions.
diff --git a/algorithms/maths/combination.py b/algorithms/maths/combination.py
@@ -1,6 +1,17 @@
 def combination(n, r):
-    # This function calculates nCr
+    """This function calculates nCr."""
     if n == r or r == 0:
         return 1
     else:
         return combination(n-1, r-1) + combination(n-1, r)
+
+def combination_memo(n, r):
+    """This function calculates nCr using memoization method."""
+    memo = {}
+    def recur(n, r):
+        if n == r or r == 0:
+            return 1
+        if (n, r) not in memo:
+            memo[(n, r)] = recur(n - 1, r - 1) + recur(n - 1, r)
+        return memo[(n, r)]
+    return recur(n, r)
diff --git a/tests/test_maths.py b/tests/test_maths.py
@@ -12,7 +12,7 @@
     pythagoras,
     is_prime,
     encrypt, decrypt, generate_key,
-    combination
+    combination, combination_memo
 )
 
 import unittest
@@ -230,7 +230,9 @@ class TestCombination(unittest.TestCase):
     def test_combination(self):
         self.assertEqual(10, combination(5, 2))
         self.assertEqual(252, combination(10, 5))
-
+    def test_combination_memo(self):
+        self.assertEqual(10272278170, combination_memo(50, 10))
+        self.assertEqual(847660528, combination_memo(40, 10))
 class TestFactorial(unittest.TestCase):
     """[summary]
     Test for the file factorial.py