Repository: keon/algorithms
Pull request #379 (2018-07-24 14:28:31)

added nearest neighbor algorithm - machine-learning
* Two functions ```nearest_neighbor(x, tSet)``` and a (eulidean) distance function ```distance(x,y)```.   
* I used the ```numpy``` library for calculating the absolute value of a vector.  
* Two trainings sets for the logical AND-function and for color-analysing (dark/light color).  

Have someone a tip for finding the ***k-nearest*** neighbors? I wrote a simple algorithm.  

- [X] **If creating a new file :**
  - [X] added links to it in the README files ?
  - [X] included tests with it ?
  - [ ] added description (overview of algorithm, time and space compleixty, 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 4cf79cb..7ef7f52 100644
--- a/README.md
+++ b/README.md
@@ -350,6 +350,8 @@ If you want to uninstall algorithms, it is as simple as:
         - [simplify_path](algorithms/unix/path/simplify_path.py)
 - [union-find](algorithms/union-find)
     - [count_islands](algorithms/union-find/count_islands.py)
+- [machine-learning](algorithms/machine-learning)
+    - [nearest neighbor classification](algorithms/machine-learning/nearest_neighbor.py)
 
 ## Contributors
 The repo is maintained by
diff --git a/README_CN.md b/README_CN.md
index c3a97c1..f3dc87f 100644
--- a/README_CN.md
+++ b/README_CN.md
@@ -1,4 +1,4 @@
-<p align="center"><img src="https://raw.githubusercontent.com/jbeguna04/algorithms/master/LogoDesins/logotype1blue.png"></p>
+<p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
 [English](README.md) | 简体中文 | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md) | [Português](README_PTBR.md)
 
@@ -79,7 +79,7 @@ pip3 uninstall -y algorithms
     - [josephus_problem: 约瑟夫问题](algorithms/arrays/josephus.py)
     - [max_ones_index](algorithms/arrays/max_ones_index.py)
     - [limit](algorithms/arrays/limit.py)
-    - [longest_non_repeat：最长不重复子串](algorithms/arrays/longest_non_repeat.py/)
+    - [longest_non_repeat：最长不重复子串](algorithms/arrays/longest_non_repeat.py/) 
     - [merge_intervals：合并重叠间隔](algorithms/arrays/merge_intervals.py)
     - [missing_ranges：遗失的范围](algorithms/arrays/missing_ranges.py)
     - [plus_one：加一运算](algorithms/arrays/plus_one.py)
diff --git a/README_GE.md b/README_GE.md
index 4f88a82..226deee 100644
--- a/README_GE.md
+++ b/README_GE.md
@@ -1,4 +1,4 @@
-<p align="center"><img src="https://raw.githubusercontent.com/jbeguna04/algorithms/master/LogoDesins/logotype1blue.png"></p>
+<p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
 [English](README.md) | [简体中文](README_CN.md) | Deutsch | [日本語](README_JP.md) | [한국어](README_KR.md) | [Português](README_PTBR.md)
 
diff --git a/README_JP.md b/README_JP.md
index 8a89bbf..7e3062e 100644
--- a/README_JP.md
+++ b/README_JP.md
@@ -1,4 +1,4 @@
-<p align="center"><img src="https://raw.githubusercontent.com/jbeguna04/algorithms/master/LogoDesins/logotype1blue.png"></p>
+<p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
 [English](README.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | 日本語 | [한국어](README_KR.md) | [Português](README_PTBR.md)
 
@@ -13,7 +13,7 @@ Pythonのデータ構造とアルゴリズム
 Python 3で開発された簡単で明確なデータ構造とアルゴリズムの例を紹介します。
 
 ## 貢献
-貢献に興味を持っていただきありがとうございます。 このプロジェクトに貢献する方法はたくさんあります。
+貢献に興味を持っていただきありがとうございます。 このプロジェクトに貢献する方法はたくさんあります。 
 
 [簡単にコミュニティへ貢献するには](CONTRIBUTING_JP.md)
 
diff --git a/README_KR.md b/README_KR.md
index c2f365e..91bfc0a 100644
--- a/README_KR.md
+++ b/README_KR.md
@@ -1,4 +1,4 @@
-<p align="center"><img src="https://raw.githubusercontent.com/jbeguna04/algorithms/master/LogoDesins/logotype1blue.png"></p>
+<p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
 [English](README.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md) | 한국어 | [Português](README_PTBR.md)
 
@@ -328,7 +328,7 @@ if __name__ == "__main__":
     - [tree](algorithms/tree/tree.py)
 - [union-find : 합집합 찾기](algorithms/union-find)
     - [count_islands](algorithms/union-find/count_islands.py)
-
+    
 ## 기여자들
 이 저장소는 아래 사람들에 의해 유지되고 있습니다.
 
diff --git a/README_PTBR.md b/README_PTBR.md
index 6f6b93a..2a9e05f 100644
--- a/README_PTBR.md
+++ b/README_PTBR.md
@@ -1,4 +1,4 @@
-<p align="center"><img src="https://raw.githubusercontent.com/jbeguna04/algorithms/master/LogoDesins/logotype1blue.png"></p>
+<p align="center"><img width="40%" src="docs/source/_static/algorithms_logo.png" /></p>
 
 [English](README.md) | [简体中文](README_CN.md) | [Deutsch](README_GE.md) | [日本語](README_JP.md) | [한국어](README_KR.md) | Português
 
diff --git a/algorithms/backtrack/subsets.py b/algorithms/backtrack/subsets.py
index 1c44302..a11c3c9 100644
--- a/algorithms/backtrack/subsets.py
+++ b/algorithms/backtrack/subsets.py
@@ -57,3 +57,8 @@ def subsets_v2(self, nums):
     for num in sorted(nums):
         res += [item+[num] for item in res]
     return res
+
+
+test = [1, 2, 3]
+print(test)
+print(subsets(test))
diff --git a/algorithms/backtrack/subsets_unique.py b/algorithms/backtrack/subsets_unique.py
index da73a25..a99f25c 100644
--- a/algorithms/backtrack/subsets_unique.py
+++ b/algorithms/backtrack/subsets_unique.py
@@ -35,3 +35,8 @@ def subsets_unique(nums):
     res = set()
     backtrack(res, nums, [], 0)
     return list(res)
+
+
+test = [1, 2, 2]
+print(test)
+print(subsets_unique(test))
diff --git a/algorithms/ml/nearest_neighbor.py b/algorithms/ml/nearest_neighbor.py
new file mode 100644
index 0000000..d0fabab
--- /dev/null
+++ b/algorithms/ml/nearest_neighbor.py
@@ -0,0 +1,41 @@
+import math
+
+def distance(x,y):
+    """[summary]
+    HELPER-FUNCTION
+    calculates the (eulidean) distance between vector x and y.
+
+    Arguments:
+        x {[tuple]} -- [vector]
+        y {[tuple]} -- [vector]
+    """
+    assert len(x) == len(y), "The vector must have same length"
+    result = ()
+    sum = 0
+    for i in range(len(x)):
+        result += (x[i] -y[i],)
+    for component in result:
+        sum += component**2
+    return math.sqrt(sum)
+
+
+def nearest_neighbor(x, tSet):
+    """[summary]
+    Implements the nearest neighbor algorithm
+
+    Arguments:
+        x {[tupel]} -- [vector]
+        tSet {[dict]} -- [training set]
+
+    Returns:
+        [type] -- [result of the AND-function]
+    """
+    assert isinstance(x, tuple) and isinstance(tSet, dict)
+    current_key = ()
+    min_d = float('inf')
+    for key in tSet:
+        d = distance(x, key)
+        if d < min_d:
+            min_d = d
+            current_key = key
+    return tSet[current_key]


Test patch:
diff --git a/algorithms/bfs/shortest_distance_from_all_buildings.py b/algorithms/bfs/shortest_distance_from_all_buildings.py
index 4d4249c..48c41d0 100644
--- a/algorithms/bfs/shortest_distance_from_all_buildings.py
+++ b/algorithms/bfs/shortest_distance_from_all_buildings.py
@@ -38,3 +38,6 @@ def bfs(grid, matrix, i, j, count):
                 matrix[k][l][0] += step+1
                 matrix[k][l][1] = count+1
                 q.append((k, l, step+1))
+
+grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
+print(shortest_distance(grid))
diff --git a/tests/test_ml.py b/tests/test_ml.py
new file mode 100644
index 0000000..61852ec
--- /dev/null
+++ b/tests/test_ml.py
@@ -0,0 +1,31 @@
+from algorithms.ml.nearest_neighbor import (
+    distance,
+    nearest_neighbor
+)
+
+import unittest
+
+class TestML(unittest.TestCase):
+    def setUp(self):
+        # train set for the AND-function
+        self.trainSetAND = {(0,0) : 0, (0,1) :0, (1,0) : 0, (1,1) : 1} 
+
+        # train set for light or dark colors
+        self.trainSetLight = {(11, 98, 237) : 'L', (3, 39, 96) : 'D', (242, 226, 12) : 'L', (99, 93, 4) : 'D',
+        (232, 62, 32) : 'L', (119, 28, 11) : 'D', (25, 214, 47) : 'L', (89, 136, 247) : 'L',
+        (21, 34, 63) : 'D', (237, 99, 120) : 'L', (73, 33, 39) : 'D'}
+    def test_nearest_neighbor(self):
+        # AND-function
+        self.assertEqual(nearest_neighbor((1,1), self.trainSetAND), 1)
+        self.assertEqual(nearest_neighbor((0,1), self.trainSetAND), 0)
+
+        # dark/light color test
+        self.assertEqual(nearest_neighbor((31, 242, 164), self.trainSetLight), 'L')
+        self.assertEqual(nearest_neighbor((13, 94, 64), self.trainSetLight), 'D')
+        self.assertEqual(nearest_neighbor((230, 52, 239), self.trainSetLight), 'L')
+    def test_distance(self):
+        self.assertAlmostEqual(distance((1,2,3), (1,0,-1)), 4.47, 2)
+
+        
+if __name__ == "__main__":
+    unittest.main()
\ No newline at end of file