Repository: keon/algorithms
Pull request #598 (2019-11-27 23:41:41)

Add recursive binomial coefficient
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [X] **If creating a new file :**
  - [X] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**



Patch:
diff --git a/README.md b/README.md
index d3bc636..d188e04 100644
--- a/README.md
+++ b/README.md
@@ -160,6 +160,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [satisfiability](algorithms/graph/satisfiability.py)
     - [tarjan](algorithms/graph/tarjan.py)
     - [traversal](algorithms/graph/traversal.py)
+    - [all_pairs_shortest_path](algorithms/graph/all_pairs_shortest_path.py)
     - [bellman_ford](algorithms/graph/bellman_ford.py)
 - [heap](algorithms/heap)
     - [merge_sorted_k_lists](algorithms/heap/merge_sorted_k_lists.py)
@@ -216,7 +217,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [sqrt_precision_factor](algorithms/maths/sqrt_precision_factor.py)
     - [summing_digits](algorithms/maths/summing_digits.py)
     - [hailstone](algorithms/maths/hailstone.py)
-	  - [find_order](algorithms/maths/find_order_simple.py)
+    - [recursive_binomial_coefficient](algorithms/maths/recursive_binomial_coefficient.py)
+    - [find_order](algorithms/maths/find_order_simple.py)
 	  - [find_primitive_root](algorithms/maths/find_primitive_root_simple.py)
 - [matrix](algorithms/matrix)
     - [sudoku_validator](algorithms/matrix/sudoku_validator.py)
diff --git a/algorithms/graph/__init__.py b/algorithms/graph/__init__.py
index 646db09..a155c77 100644
--- a/algorithms/graph/__init__.py
+++ b/algorithms/graph/__init__.py
@@ -1,3 +1,4 @@
 from .tarjan import *
 from .check_bipartite import *
+from .all_pairs_shortest_path import *
 from .bellman_ford import *
diff --git a/algorithms/maths/recursive_binomial_coefficient.py b/algorithms/maths/recursive_binomial_coefficient.py
new file mode 100644
index 0000000..ae57bd6
--- /dev/null
+++ b/algorithms/maths/recursive_binomial_coefficient.py
@@ -0,0 +1,28 @@
+def recursive_binomial_coefficient(n,k):
+    """Calculates the binomial coefficient, C(n,k), with n>=k using recursion
+    Time complexity is O(k), so can calculate fairly quickly for large values of k.
+
+    >>> recursive_binomial_coefficient(5,0)
+    1
+
+    >>> recursive_binomial_coefficient(8,2)
+    28
+
+    >>> recursive_binomial_coefficient(500,300)
+    5054949849935535817667719165973249533761635252733275327088189563256013971725761702359997954491403585396607971745777019273390505201262259748208640
+
+    """
+
+    if k>n:
+        raise ValueError('Invalid Inputs, ensure that n >= k')
+        #function is only defined for n>=k
+    if k == 0 or n == k:
+        #C(n,0) = C(n,n) = 1, so this is our base case.
+        return 1
+    if k > n/2:
+        #C(n,k) = C(n,n-k), so if n/2 is sufficiently small, we can reduce the problem size.
+        return recursive_binomial_coefficient(n,n-k)
+    else:
+        #else, we know C(n,k) = (n/k)C(n-1,k-1), so we can use this to reduce our problem size.
+        return int((n/k)*recursive_binomial_coefficient(n-1,k-1))
+


Test patch:
diff --git a/algorithms/graph/all_pairs_shortest_path.py b/algorithms/graph/all_pairs_shortest_path.py
new file mode 100644
index 0000000..46f3b7c
--- /dev/null
+++ b/algorithms/graph/all_pairs_shortest_path.py
@@ -0,0 +1,28 @@
+"""
+Given a n*n adjacency array.
+it will give you all pairs shortest path length.
+use deepcopy to preserve the original information.
+
+Time complexity : O(E^3)
+
+example
+
+a = [[0, 0.1, 0.101, 0.142, 0.277], [0.465, 0, 0.191, 0.192, 0.587], [0.245, 0.554, 0, 0.333, 0.931], [1.032, 0.668, 0.656, 0, 0.151], [0.867, 0.119, 0.352, 0.398, 0]]
+
+result 
+
+[[0, 0.1, 0.101, 0.142, 0.277], [0.436, 0, 0.191, 0.192, 0.34299999999999997], [0.245, 0.345, 0, 0.333, 0.484], [0.706, 0.27, 0.46099999999999997, 0, 0.151], [0.5549999999999999, 0.119, 0.31, 0.311, 0]]
+
+"""
+import copy
+
+def all_pairs_shortest_path(adjacency_matrix):
+    new_array = copy.deepcopy(adjacency_matrix)
+
+    for k in range(len(new_array)):
+        for i in range(len(new_array)):
+            for j in range(len(new_array)):
+                if new_array[i][j] > new_array[i][k] + new_array[k][j]:
+                    new_array[i][j] = new_array[i][k] + new_array[k][j]           
+    
+    return new_array
\ No newline at end of file
diff --git a/tests/test_graph.py b/tests/test_graph.py
index 699136a..48c2bbb 100644
--- a/tests/test_graph.py
+++ b/tests/test_graph.py
@@ -1,6 +1,7 @@
 from algorithms.graph import Tarjan
 from algorithms.graph import check_bipartite
 from algorithms.graph.dijkstra import Dijkstra
+from algorithms.graph import all_pairs_shortest_path
 from algorithms.graph import bellman_ford
 
 import unittest
@@ -75,7 +76,19 @@ class TestDijkstra(unittest.TestCase):
            [0, 0, 2, 0, 0, 0, 6, 7, 0] 
           ]; 
 
-        self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14]);
+        self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14])
+
+class TestAll_Pairs_Shortest_Path(unittest.TestCase):
+    
+    def test_all_pairs_shortest_path(self):
+        graph = [[0, 0.1, 0.101, 0.142, 0.277], 
+                 [0.465, 0, 0.191, 0.192, 0.587], 
+                 [0.245, 0.554, 0, 0.333, 0.931], 
+                 [1.032, 0.668, 0.656, 0, 0.151], 
+                 [0.867, 0.119, 0.352, 0.398, 0]]
+        result = all_pairs_shortest_path(graph)
+
+        self.assertEqual(result, [[0, 0.1, 0.101, 0.142, 0.277], [0.436, 0, 0.191, 0.192, 0.34299999999999997], [0.245, 0.345, 0, 0.333, 0.484], [0.706, 0.27, 0.46099999999999997, 0, 0.151], [0.5549999999999999, 0.119, 0.31, 0.311, 0]])
         
 class TestBellmanFord(unittest.TestCase):
     def test_bellman_ford(self):