How to Flatten an Irregular List of Lists in Python?

Introduction

Python provides several ways to flatten a list, but most solutions fail when dealing with irregular or arbitrarily nested lists. In this article, we will explore the problem of flattening such lists and discuss the best approach to solve it. We will also provide a comprehensive code example that handles arbitrary nesting and can be used as a solution.

The Problem

Consider the following list: [[[1, 2, 3], [4, 5]], 6]. The desired output is [1, 2, 3, 4, 5, 6]. This list is irregular or arbitrarily nested, meaning it contains nested lists to an arbitrary depth. The challenge is to flatten this irregular list and obtain a single flat list.

Existing Solutions

Existing solutions to flatten lists in Python often fail to handle the case of irregular nesting. Some solutions work only for shallow lists, while others only work for a specific level of nesting.

For example, a common solution is to use nested loops and append elements to a new list:


def flatten(lst):
    result = []
    for sublist in lst:
        for element in sublist:
            result.append(element)
    return result
        

However, this solution only works for a specific level of nesting and does not handle arbitrary nesting.

The Best Approach

The best approach to flatten an irregular list of lists in Python is to use recursion. Recursion allows us to handle arbitrary nesting by repeatedly applying the flatten operation until we reach the base case, which is a non-iterable element. Here is an optimized recursive solution:


def flatten(lst):
    result = []
    for element in lst:
        if hasattr(element, "__iter__") and not isinstance(element, str):
            result.extend(flatten(element))
        else:
            result.append(element)
    return result
        

This solution checks if an element is iterable but not a string (to avoid flattening strings as well) using the hasattr and isinstance functions. If the element is iterable, it recursively calls the flatten function on that element. If the element is not iterable, it is appended to the result list.

Example

Let's see the solution in action with the given example of [[[1, 2, 3], [4, 5]], 6]:


nested_list = [[[1, 2, 3], [4, 5]], 6]
flattened_list = flatten(nested_list)
print(flattened_list)
        

The output will be:


[1, 2, 3, 4, 5, 6]
        

Optimizations

The provided solution can be optimized for performance by using a generator instead of a list. A generator is more memory-efficient because it produces elements on the fly as requested, rather than storing them all in memory at once. Here is the optimized version of the solution:


def flatten(lst):
    for element in lst:
        if hasattr(element, "__iter__") and not isinstance(element, str):
            yield from flatten(element)
        else:
            yield element
        

This version uses the yield keyword to create a generator. The yield from statement allows us to yield elements from a nested generator directly instead of iterating over each element.

Conclusion

Flattening irregular or arbitrarily nested lists is a common problem in Python programming. While there are existing solutions, most of them fail when dealing with arbitrary nesting. The best approach is to use recursion, which allows us to handle arbitrary nesting and provide a reliable solution. Additionally, optimizing the solution by using a generator instead of a list can improve memory efficiency.

By using the provided code examples, you can easily flatten irregular lists and obtain a single flat list in Python.