Repository: keon/algorithms
Pull request #487 (2019-03-09 02:36:56)

 fix bugs, add descriptions, and add tests
1. Fixed some bugs in "permute.py", "subsets.py"
2. Updated description for the algorithm in "palindrome_partitioning.py"
3. Added tests for the algorithm in "test_backtrack.py"

coveralls: ## Pull Request Test Coverage Report for [Build 873](https://coveralls.io/builds/22079811)

* **62** of **62**   **(100.0%)**  changed or added relevant lines in **3** files are covered.
* **2** unchanged lines in **1** file lost coverage.
* Overall coverage increased (+**1.0%**) to **67.223%**

---


|  Files with Coverage Reduction | New Missed Lines | % |
| :-----|--------------|--: |
| [algorithms/sort/top_sort.py](https://coveralls.io/builds/22079811/source?filename=algorithms%2Fsort%2Ftop_sort.py#L41) | 2 | 90.38% |
<!-- | **Total:** | **2** |  | -->

|  Totals | [![Coverage Status](https://coveralls.io/builds/22079811/badge)](https://coveralls.io/builds/22079811) |
| :-- | --: |
| Change from base [Build 872](https://coveralls.io/builds/22060441): |  1.0% |
| Covered Lines: | 4754 |
| Relevant Lines: | 7072 |

---
##### 💛  - [Coveralls](https://coveralls.io)


Patch:
diff --git a/algorithms/backtrack/palindrome_partitioning.py b/algorithms/backtrack/palindrome_partitioning.py
index 052339d..10f1da9 100644
--- a/algorithms/backtrack/palindrome_partitioning.py
+++ b/algorithms/backtrack/palindrome_partitioning.py
@@ -3,6 +3,9 @@ but rather for all the ways you can divide the input string
 up into palindromic substrings.
 (There's always at least one way,
 since one-character substrings are always palindromes.)
+
+ex)
+'abcbab' => [['abcba', 'b'], ['a', 'bcb', 'a', 'b'], ['a', 'b', 'c', 'bab'], ['a', 'b', 'c', 'b', 'a', 'b']]
 """
 
 
diff --git a/algorithms/backtrack/permute.py b/algorithms/backtrack/permute.py
index 4ce4843..27c7d97 100644
--- a/algorithms/backtrack/permute.py
+++ b/algorithms/backtrack/permute.py
@@ -19,7 +19,7 @@ def permute(elements):
         returns a list with the permuations.
     """
     if len(elements) <= 1:
-        return elements
+        return [elements]
     else:
         tmp = []
         for perm in permute(elements[1:]):
diff --git a/algorithms/backtrack/subsets.py b/algorithms/backtrack/subsets.py
index 1c44302..56eef44 100644
--- a/algorithms/backtrack/subsets.py
+++ b/algorithms/backtrack/subsets.py
@@ -52,7 +52,7 @@ def backtrack(res, nums, cur, pos):
 
 
 # Iteratively
-def subsets_v2(self, nums):
+def subsets_v2(nums):
     res = [[]]
     for num in sorted(nums):
         res += [item+[num] for item in res]


Test patch:
diff --git a/tests/test_backtrack.py b/tests/test_backtrack.py
index cb0838a..682a89b 100644
--- a/tests/test_backtrack.py
+++ b/tests/test_backtrack.py
@@ -13,7 +13,14 @@ from algorithms.backtrack import (
     generate_parenthesis_v1,
     generate_parenthesis_v2,
     letter_combinations,
+    palindromic_substrings,
     pattern_match,
+    permute_unique,
+    permute,
+    permute_recursive,
+    subsets_unique,
+    subsets,
+    subsets_v2,
 )
 
 import unittest
@@ -261,6 +268,106 @@ class TestLetterCombinations(unittest.TestCase):
         self.assertEqual(sorted(letter_combinations(digit2)), sorted(answer2))
 
 
+class TestPalindromicSubstrings(unittest.TestCase):
+
+    def test_palindromic_substrings(self):
+        string1 = "abc"
+        answer1 = [['a', 'b', 'c']]
+        self.assertEqual(palindromic_substrings(string1), sorted(answer1))
+
+        string2 = "abcba"
+        answer2 = [['abcba'], ['a', 'bcb', 'a'], ['a', 'b', 'c', 'b', 'a']]
+        self.assertEqual(sorted(palindromic_substrings(string2)), sorted(answer2))
+
+        string3 = "abcccba"
+        answer3 = [['abcccba'], ['a', 'bcccb', 'a'], ['a', 'b', 'ccc', 'b', 'a'],
+            ['a', 'b', 'cc', 'c', 'b', 'a'], ['a', 'b', 'c', 'cc', 'b', 'a'], 
+            ['a', 'b', 'c', 'c', 'c', 'b', 'a']]
+        self.assertEqual(sorted(palindromic_substrings(string3)), sorted(answer3))
+
+
+class TestPermuteUnique(unittest.TestCase):
+
+    def test_permute_unique(self):
+        nums1 = [1, 1, 2]
+        answer1 = [[2, 1, 1], [1, 2, 1], [1, 1, 2]]
+        self.assertEqual(sorted(permute_unique(nums1)), sorted(answer1))
+
+        nums2 = [1, 2, 1, 3]
+        answer2 = [[3, 1, 2, 1], [1, 3, 2, 1], [1, 2, 3, 1], [1, 2, 1, 3], [3, 2, 1, 1], 
+            [2, 3, 1, 1], [2, 1, 3, 1], [2, 1, 1, 3], [3, 1, 1, 2], [1, 3, 1, 2], [1, 1, 3, 2], [1, 1, 2, 3]]
+        self.assertEqual(sorted(permute_unique(nums2)), sorted(answer2))
+
+        nums3 = [1, 2, 3]
+        answer3 = [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
+        self.assertEqual(sorted(permute_unique(nums3)), sorted(answer3))
+
+
+class TestPermute(unittest.TestCase):
+
+    def test_permute(self):
+        nums1 = [1, 2, 3, 4]
+        answer1 = [[1, 2, 3, 4], [2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1], [1, 3, 2, 4], 
+            [3, 1, 2, 4], [3, 2, 1, 4], [3, 2, 4, 1], [1, 3, 4, 2], [3, 1, 4, 2], 
+            [3, 4, 1, 2], [3, 4, 2, 1], [1, 2, 4, 3], [2, 1, 4, 3], [2, 4, 1, 3], 
+            [2, 4, 3, 1], [1, 4, 2, 3], [4, 1, 2, 3], [4, 2, 1, 3], [4, 2, 3, 1], 
+            [1, 4, 3, 2], [4, 1, 3, 2], [4, 3, 1, 2], [4, 3, 2, 1]]
+        self.assertEqual(sorted(permute(nums1)), sorted(answer1))
+
+        nums2 = [1, 2, 3]
+        answer2 = [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
+        self.assertEqual(sorted(permute(nums2)), sorted(answer2))
+
+    def test_permute_recursive(self):
+        nums1 = [1, 2, 3, 4]
+        answer1 = [[1, 2, 3, 4], [2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1], [1, 3, 2, 4], 
+            [3, 1, 2, 4], [3, 2, 1, 4], [3, 2, 4, 1], [1, 3, 4, 2], [3, 1, 4, 2], 
+            [3, 4, 1, 2], [3, 4, 2, 1], [1, 2, 4, 3], [2, 1, 4, 3], [2, 4, 1, 3], 
+            [2, 4, 3, 1], [1, 4, 2, 3], [4, 1, 2, 3], [4, 2, 1, 3], [4, 2, 3, 1], 
+            [1, 4, 3, 2], [4, 1, 3, 2], [4, 3, 1, 2], [4, 3, 2, 1]]
+        self.assertEqual(sorted(permute_recursive(nums1)), sorted(answer1))
+
+        nums2 = [1, 2, 3]
+        answer2 = [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
+        self.assertEqual(sorted(permute_recursive(nums2)), sorted(answer2))
+
+
+class TestSubsetsUnique(unittest.TestCase):
+
+    def test_subsets_unique(self):
+        nums1 = [1, 2, 2]
+        answer1 = [(1, 2), (1,), (1, 2, 2), (2,), (), (2, 2)]
+        self.assertEqual(sorted(subsets_unique(nums1)), sorted(answer1))
+
+        nums2 = [1, 2, 3, 4]
+        answer2 = [(1, 2), (1, 3), (1, 2, 3, 4), (1,), (2,), (3,), (1, 4), (1, 2, 3), 
+            (4,), (), (2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (3, 4), (2, 4)]
+        self.assertEqual(sorted(subsets_unique(nums2)), sorted(answer2))
+
+
+class TestSubsets(unittest.TestCase):
+
+    def test_subsets(self):
+        nums1 = [1, 2, 3]
+        answer1 = [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
+        self.assertEqual(sorted(subsets(nums1)), sorted(answer1))
+
+        nums2 = [1, 2, 3, 4]
+        answer2 = [[1, 2, 3, 4], [1, 2, 3], [1, 2, 4], [1, 2], [1, 3, 4], 
+            [1, 3], [1, 4], [1], [2, 3, 4], [2, 3], [2, 4], [2], [3, 4], [3], [4], []]
+        self.assertEqual(sorted(subsets(nums2)), sorted(answer2))
+
+    def test_subsets_v2(self):
+        nums1 = [1, 2, 3]
+        answer1 = [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
+        self.assertEqual(sorted(subsets_v2(nums1)), sorted(answer1))
+
+        nums2 = [1, 2, 3, 4]
+        answer2 = [[1, 2, 3, 4], [1, 2, 3], [1, 2, 4], [1, 2], [1, 3, 4], 
+            [1, 3], [1, 4], [1], [2, 3, 4], [2, 3], [2, 4], [2], [3, 4], [3], [4], []]
+        self.assertEqual(sorted(subsets_v2(nums2)), sorted(answer2))
+
+
 if __name__ == '__main__':
 
     unittest.main()