Generating all permutations of a sequence

Question

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()

Answer 1

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 to 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:
  • Change iterable to elements – Maybe this is just me, but it felt wrong using iterable. I think elements convey the intention much better
  • Change sequence to 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
  • Change insert_at() to something else – An insert method intuitively changes a list, whilst you create a new list with an inserted element.

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.

Answer 2

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.