Welcome, guest | Sign In | My Account | Store | Cart

Flattening an arbitrarily nested list in Python (Python recipe) by Vasudev Ram
ActiveState Code (http://code.activestate.com/recipes/578948/)

This is a recipe to flatten a Python list which may have nested lists as items within it. It works for lists that have a maximum depth of nesting roughly equal to the recursion depth limit of Python, which is set to 1000 by default, though it can be increased with sys.setrecursionlimit().

Python, 41 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# Program to flatten an arbitrarily nested list.

def nested_item(depth, value):
    if depth <= 1:
        return [value]
    else:
        return [nested_item(depth - 1, value)]

def nested_list(n):
    """Generate a nested list where the i'th item is at depth i."""
    lis = []
    for i in range(n):
        if i == 0:
            lis.append(i)
        else:
            lis.append(nested_item(i, i))
    return lis

def flatten(lis):
    """Given a list, possibly nested to any level, return it flattened."""
    new_lis = []
    for item in lis:
        if type(item) == type([]):
            new_lis.extend(flatten(item))
        else:
            new_lis.append(item)
    return new_lis

for n in range(7):
    print n,
    lis = nested_list(n)
    print "original:", lis
    new_lis = flatten(lis)
    print "flattened:", new_lis
    print

for i in range(6):
    lis = range(i)
    print "orig:", lis
    flat_lis = flatten(lis)
    print "flat:", flat_lis

This task can come up in any case where you have a nested list (which contains some (non-list) items and some lists in it, and the inner lists themselves have items in them. If you want to convert to the list to a flat list, this solution can help. Known issue: the solution uses a recursive flatten() function, which will not work if the depth of recursion exceeds about 1000.

The nested_list() function in the recipe generates nested lists for testing the solution. It calls a helper function, nested_item(), which is recursive.

The flatten() function which flattens the list, is also recursive.

More details are available at this blog post:

http://jugad2.blogspot.in/2014/10/flattening-arbitrarily-nested-list-in.html

That post also has multiple comments that show or link to alternative solutions, including some that use Python 3 features like "yield from".

Tags: algorithm, algorithms, flatten, list, lists, python