import itertools
def permutation_lib(iterable):
return itertools.permutations(iterable)
def permutation(iterable):
if len(iterable) <= 1:
yield tuple(iterable)
else:
for sequence in permutation(iterable[:-1]):
for i in range(len(sequence)+1):
yield insert_at(sequence, i, iterable[-1])
def insert_at(iterable, idx, value):
if idx == 0:
return (value,) + iterable[:]
elif idx == len(iterable):
return iterable[:] + (value,)
else:
return iterable[:idx] + (value,) + iterable[idx:]
import unittest
class TestPermutation(unittest.TestCase):
def test_permutations(self):
self.assertEqual(list(permutation([0])), list(permutation_lib([0])))
self.assertEqual(sorted(list(permutation([0,1]))), list(permutation_lib([0, 1])))
if __name__ == '__main__':
unittest.main()
-
\$\begingroup\$ You've posted many questions in the last few weeks, don't forget to reiterate over your older questions, and accept the answers you find most useful, or comment upon the particular question as to why you can't accept any of the given answers. \$\endgroup\$ – holroy Nov 4 '15 at 14:33
-
\$\begingroup\$ @holroy Sure thing, usually I sit in weekends to review all my question and possible answers before accepting them. \$\endgroup\$ – CodeYogi Nov 5 '15 at 5:39
Here is some thoughts on naming, coding and testing.
Naming of methods and variables
Let me start by stating that naming is hard, and is related to personal taste and habits. So the following suggestions are not meant to be written in stone, but is my personal suggestion:
Change
permutation
topermutations
– Your method returns a list of permutations, not a single permutation. (Or actually it returns a generator, but still a generator is more of a plural object than a singular object)Naming of test methods – One suggestion regarding name of test methods states that the name should reflect which method you are testing, the input you are giving and the expected output. That bargains for really long names. One way to simplify this is to use multiple classes, and let each class test one function. Then you get something like:
class TestPermutations(unittest.TestCase): """Tests variuous variants of permutations().""" def test_single_element(self): """Test with a single element.""" pass def test_list_of_two_elements(self): """Test with a single element.""" pass def test_string(self): """Test with a string.""" pass
Also note that each test method should in normal circumstances only test one thing!
- Some more questionable renames:
- Change
iterable
toelements
– Maybe this is just me, but it felt wrong usingiterable
. I thinkelements
convey the intention much better - Change
sequence
tosub_permutation
– This, to me, conveys better that here is where the recursion has occured, and this is what we use to build the final permutations generator - Change
insert_at()
to something else – An insert method intuitively changes a list, whilst you create a new list with an inserted element.
- Change
Code review
There is not much to review, but if you are aiming to reinvent the itertools.permutations()
, you should aim for getting the same list, and not having to resort to sorting the list afterwards. Or put another way, your permutation()
doesn't return the natural order of permutations. If permutating "ABC", we sort of expect to get "ABC", "ACB", "BAC", "BCA", "CAB", "CBA", in that order. This can be achieved by switching around the for
loops.
Your insert_at()
is not actually needed, as you can do the same using a little trick related to sliceing. Your yield insert_at(...)
can be replaced with:
yield sequence[:i] + tuple(iterable[-1]) + sequence[i:]
Combing these two, and changing names, we end up with:
def permutations(elements):
"""Return generator presenting all permutations of elements."""
if len(elements) <= 1:
yield tuple(elements)
else:
for idx in range(len(elements)):
for sub_permutation in permutations(elements[:idx] + elements[idx+1:]):
yield tuple(elements[idx:idx+1]) + sub_permutation
I don't really see the need for the permutations_lib()
as it only hides your test verification against itertools.permutations()
. My suggestion is therefore to remove this method, and use the original directly.
Test review
As stated already, you could work on naming your tests and splitting them up so that each function tests only one variant for a given method. In addition I would like to focus on the AAA-pattern of unit testing:
- Arrange - Setup for your unit test
- Act - Do the actual test
- Assert - Do the assertion, but no more actions
This pattern, when followed, ensures a good readability of your tests, and can help you avoid doing multiple action or assertions when you shouldn't.
So here are some tests for the new version of permutations()
:
import unittest
import types
class TestPermutations(unittest.TestCase):
# Various test cases
numeric_list = [5, 6, 7]
alpha_list = ['aa', 'bb', 'cc' ]
string = 'ABCDEF'
single_element = [4]
list_of_lists = [ [1.1, 1.2], [2.1, 2.2], [3.1, 3.2] ]
multilist = [ 'a', 2, 3.3 ]
def generic_test(self, elements):
"""Compares itertools.permutations(elements) vs permutations(elements)."""
# Arrange
expected = list(itertools.permutations(elements))
# Act
actual = list(permutations(elements))
# Assert
self.assertEqual(expected, actual)
def test_is_generator(self):
"""Test that object is actually an generator."""
# Act
actual = permutations(self.numeric_list)
# Assert
self.assertTrue( isinstance(actual, types.GeneratorType))
def test_numeric_list(self):
"""Test for a list of numbers"""
self.generic_test(self.numeric_list)
def test_alpha_list(self):
"""Test for a list of strings"""
self.generic_test(self.alpha_list)
def test_string(self):
"""Test for a single string."""
self.generic_test(self.string)
def test_single_element(self):
"""Test for a single element."""
self.generic_test(self.single_element)
def test_list_of_lists(self):
"""Test for a list of lists."""
self.generic_test(self.list_of_lists)
def test_multilist(self):
"""Test for list consisting of various elements."""
self.generic_test(self.multilist)
if __name__ == '__main__':
unittest.main()
In this test suite almost all test functions call the generic_test()
, which in other languages could be done with just one parametrized test method. This is not supported out of the box in Python, but you can read more on that subject here which present alternate methods of achieving the same effect.
Imports should always be at the top of the file. I would make an exception for those that are needed only if __name__ == '__main__'
, but in that case they should be within that block. So your code should look like:
import itertools
def permutation_lib(iterable):
...
def permutation(iterable):
...
def insert_at(iterable, idx, value):
...
if __name__ == '__main__':
import unittest
class TestPermutation(unittest.TestCase):
...
unittest.main()
which also means that when you import from this script you don't get the test class, or have import unittest
at the top with import itertools
.
None of your functions/classes/methods have docstrings. Including these to explain what each one does, and even document the parameters, return values, etc. (I like the Google style for this) makes your code easier to follow.
You have one test method with two assertions covering three functions. Does this not seem odd to you? If that method fails, where do you look for the problem? I would suggest factoring out permutation_lib
entirely (which also means you can move import itertools
to the testing block) and testing insert_at
on its own in a separate method.
-
1\$\begingroup\$ @CodeYogi there's no need to comment "+1" (especially not if you aren't actually going to vote accordingly!) \$\endgroup\$ – jonrsharpe Nov 4 '15 at 13:56