Monday, March 14, 2011

Flattening abitrarily nested lists in Python

Lists are one of the three most important data structures in Python, other being dict and str, (tuple is the younger cousin  of list). The lists can be arbitrarily nested with any kind of data inside them, e.g.

['a', [1, 2], (3, 4, 5, [7, 8, ['gnu', 'linux']]), ['a', 'b', 'c'], [['d', 'e', 'f'], 12, [13, [14, [15,]]]]]


The objective is flatten nested lists of this kind to a single list. It can be simply stated as to remove all square brackets (and parenthesis) and retain only square brackets at the end, while maintaining the order of the items as they appear in the nested list. One of the simple solution can be:

def flatten(l):
    '''Flatten a arbitrarily nested lists and return the result as a single list.
    '''
    ret = []
    for i in l:
        if isinstance(i, list) or isinstance(i, tuple):
            ret.extend(flatten(i))
        else:
            ret.append(i)
    return ret


Run this on the example and you get:

['a', 1, 2, 3, 4, 5, 7, 8, 'gnu', 'linux', 'a', 'b', 'c', 'd', 'e', 'f', 12, 13, 14, 15]


Can this be made more Pythonic and efficient. Any ides?

4 comments:

Swapz said...

Good one!

Vaibhav Bajpai said...

nice, minor improvement?

def flatten(l):
ret = []
for i in l:
if isinstance(i, (list, tuple)): ret.extend(flatten(i))
else: ret.append(i)
return ret

Ravi said...

Wow! I didn't know of that use of isinstance.

Anonymous said...

You will have a stack overflow if your list is more deeply nested than Python's stack overflow limit. Here's a solution: http://stackoverflow.com/a/20495215/509706