Problem Solving with Python: Generics

Nishant Sharma

4 min readMar 13, 2024

[1] gives a nice introduction to Generics in Python.

Let us combine Generics with a simple problem.

The problem is to find all permutations of a list. The idea for doing so is discussed in many texts including [2].

The idea is visually represented in the illustrations below:

Illustration step 1: 1 is popped from the original list and added to the result list (as a list containing 1). The result list is a list of lists.

Illustration step 2: 2 is adjusted at all possible positions for the list containing the single element 1.

Illustration step 3: 3 is adjusted at all possible positions for each element of the result list.

and so on…

The Python implementation is so:

Mandatory imports:

from typing import List, TypeVar

# Type T bound to integers and strings (or characters)
T = TypeVar("T", int, str)

Now, a method that inserts an element at a given index in a list and returns the new list. Notice that the list can be of type integer or strings as defined above by T. Explicit return type is also mentioned following the → symbol.

# insert ele at index in alist
def insert_at_index(alist: List[T], index: int, ele: T) -> List[T]:
    return_list = alist.copy()
    return_list.insert (index, ele)
    return return_list

The input list [1, 2, 3, 4] is of type List[int].

Next, we define a method that takes a count, a list, and an element and returns a list of lists with the element inserted at all positions between 0 and count-1 in the input list.

# insert ele in all indices less than count in alist
# using the function insert_at_index 
def inserts_on_indices_less_than_count (count:int, alist: List[T],ele: T) -> List[List[T]]:
    return_list = []
    for i in range (count):
        return_list += [insert_at_index (alist.copy(), i, ele)]
    return return_list

Here is an example:

Count is 2. 5 inserted at position 0 and position 1 creating two resultant lists from the original (input) list [1, 2, 3, 4].

Next, we create a future result list in the intuitive way of inserting the next element from alist in all possible positions in each popped element of the current result list. The visualization shown above helps us understand the thought process.

def all_permutations (alist: List[T]) -> List [List[T]]:
    
    # Add the first element from alist as a list
    # of single element in the result list
    # provided that the list alist is not empty
    result_list = [[alist.pop (0)]] if alist != [] else []
    
    while alist != []:
        # 1. Pop the current first element from alist (_next) 
        # 2. For each element of the current result list:
        #    a. Pop the element from the current result list for processing 
        #    b. Insert _next at all possible n+1 indices (n being the length of the element) and append it to the future result list
        # 3. n is going to be the same for all elements of the current result list
        _next = alist.pop(0) # Next in alist
        l = len (result_list) # Length of the current result list
        n = len (result_list [0]) # Common length of each element 
                                  # in the current result list
        for k in range (l):
            # Pop the elements of the current result list one by one for processing
            ele = result_list.pop(0)
            # Process each element with _next (see visualization for graphical intuition) and create the future result list
            result_list += inserts_on_indices_less_than_count (n+1, ele, _next)
    return result_list

Following is the output:

For a list of 3 distinct elements, there should be 6 permutations given by 3!.

As a side note, if you wish to avoid tampering with the original list, you may send a copy of the list to a method (that uses submethods like pop).

We get a similar output for a list of characters.

What if we define alist as:

alist: List[float] = [True,False,True]

Unfortunately, Python still returns the 6 possible permutations without any complaint. But, it violates our initial binding on T to be a list of either integers or strings (characters) only.

To get the much-desired warning, we must run the Python script using mypy (https://mypy.readthedocs.io/en/stable/getting_started.html).