top_1.py & trimmean.py created (keon#345)

aig031 · keon · commit 5982b36dfc4e · 2018-06-10T06:29:03.000-04:00
* Create top_1.py

* Create trimmean.py

* Rename top_1.py to algorithms/arrays/top_1.py

* Rename trimmean.py to algorithms/arrays/trimmean.py

* Update __init__.py

* Update README.md

* Update README_CN.md

* Update README_CN.md

* Update README_GE.md

* Update README_JP.md

* Update README_KR.md

* Update test_array.py

* Update test_array.py

* Update test_array.py
diff --git a/README.md b/README.md
@@ -68,6 +68,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack](algorithms/backtrack)
diff --git a/README_CN.md b/README_CN.md
@@ -85,6 +85,8 @@ pip3 uninstall -y algorithms
     - [rotate：反转数组](algorithms/arrays/rotate.py)
     - [summarize_ranges：数组范围](algorithms/arrays/summarize_ranges.py)
     - [three_sum：三数和为零](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum：两数和](algorithms/arrays/two_sum.py)
     - [move_zeros: 0后置问题](algorithms/arrays/move_zeros.py)
 - [backtrack：回溯](algorithms/backtrack)
diff --git a/README_GE.md b/README_GE.md
@@ -75,6 +75,8 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack](algorithms/backtrack)
diff --git a/README_JP.md b/README_JP.md
@@ -69,6 +69,8 @@ if __name__ == "__main__":
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack : バックトラッキング](algorithms/backtrack)
diff --git a/README_KR.md b/README_KR.md
@@ -68,6 +68,8 @@ if __name__ == "__main__":
     - [rotate](algorithms/arrays/rotate.py)
     - [summarize_ranges](algorithms/arrays/summarize_ranges.py)
     - [three_sum](algorithms/arrays/three_sum.py)
+    - [trimmean](algorithms/arrays/trimmean.py)
+    - [top_1](algorithms/arrays/top_1.py)
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
 - [backtrack : 백트래킹](algorithms/backtrack)
diff --git a/algorithms/arrays/__init__.py b/algorithms/arrays/__init__.py
@@ -11,4 +11,6 @@
 from .rotate import *
 from .summarize_ranges import *
 from .three_sum import *
+from .trimmean import *
+from .top_1 import *
 from .two_sum import *
diff --git a/algorithms/arrays/top_1.py b/algorithms/arrays/top_1.py
@@ -0,0 +1,32 @@
+"""
+this algorithms receive array and check most_frequent_value(a.k.a mode). Also, sometimes it can be have numerous most_frequent_value,
+so this funtion returns list. This result can be used as finding representative value on array.
+
+This algorithms get array, and make dictionary of it, find most frequent count, and make result list.
+
+For example) top_1([1, 1, 2, 2, 3, 4]) will return [1, 2]
+
+Complexity: O(n)
+"""
+def top_1(arr):
+    values = {}
+    #reserve each value which first appears on keys
+    #reserve how many time each value appears by index number on values
+    result = []
+    f_val = 0
+
+    for i in arr:
+        if i in values:
+            values[i] += 1
+        else:
+            values[i] = 1
+
+    f_val = max(values.values())
+        
+    for i in values.keys():
+        if values[i] == f_val:
+            result.append(i)
+        else:
+            continue
+    
+    return result
diff --git a/algorithms/arrays/trimmean.py b/algorithms/arrays/trimmean.py
@@ -0,0 +1,22 @@
+"""
+When make reliable means, we need to neglect best and worst value. For example, when making average score on athletes we need this option.
+So, this algorithms, fix some percentage to neglect when making mean. For example, if you suggest 20%, it will neglect best 10% value, and
+worst 10% value.
+
+This algorithm gets array and percentage to neglect. After sorted, if index of array is larger or smaller or wanted ratio, we don't
+compute it.
+
+Compleity: O(n)
+"""
+def trimmean(arr, per):
+    ratio = per/200
+    # /100 for easy calculation by *, and /2 for easy adaption to best and worst parts.
+    cal_sum = 0
+    # sum value to be calculated to trimmean.
+    arr.sort()
+    neg_val = int(len(arr)*ratio)
+    arr = arr[neg_val:len(arr)-neg_val]
+    for i in arr:
+        cal_sum += i
+    #print(cal_sum, len(arr))
+    return cal_sum/len(arr)
diff --git a/tests/test_array.py b/tests/test_array.py
@@ -12,7 +12,9 @@
     summarize_ranges,
     three_sum,
     two_sum,
-    max_ones_index
+    max_ones_index,
+    trimmean,
+    top_1
 )
 
 import unittest
@@ -306,6 +308,20 @@ def test_two_sum(self):
         self.assertTupleEqual((0, 3), two_sum([-3, 5, 2, 3, 8, -9], target=0))
 
         self.assertIsNone(two_sum([-3, 5, 2, 3, 8, -9], target=6))
+        
+class TestTrimmean(unittest.TestCase):
+
+    def test_trimmean(self):
+
+        self.assertEqual(trimmean([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 20), 5.5)
+        self.assertEqual(trimmean([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 20), 6.0)
+        
+class TestTop1(unittest.TestCase):
+    
+    def test_top_1(self):
+        self.assertListEqual(top_1([1 , 1, 2, 2, 3]), [1, 2])
+        self.assertListEqual(top_1([1, 2, 3, 324, 234, 23, 23, 1, 23, 23]), [23])
+
 
 
 if __name__ == '__main__':
