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()), list(permutation_lib())) self.assertEqual(sorted(list(permutation([0,1]))), list(permutation_lib([0, 1]))) if __name__ == '__main__': unittest.main()
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:
permutations– 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:
elements– Maybe this is just me, but it felt wrong using
iterable. I think
elementsconvey the intention much better
sub_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
insert_at()to something else – An insert method intuitively changes a list, whilst you create a new list with an inserted element.
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
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.
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
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 =  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
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.