# How to flatten an irregular list of lists? [Answered]

### Sample problem:

Yes, I know this subject has been covered before, but as far as I know, all solutions, except for one, fail on a list like this:

``````L = [[[1, 2, 3], [4, 5]], 6]
``````

Where the desired output is

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

Or perhaps even better, an iterator. The only solution I saw that works for an arbitrary nesting is this:

``````def flatten(x):
result = []
for el in x:
if hasattr(el, "__iter__") and not isinstance(el, basestring):
result.extend(flatten(el))
else:
result.append(el)
return result

flatten(L)
``````

Is this the best model? Did I overlook something? Any problems?

## Flatten an irregular list of lists in Python- Answer #1:

Using generator functions can make your example a little easier to read and probably boost the performance.

## Python 2

``````def flatten(l):
for el in l:
if isinstance(el, collections.Iterable) and not isinstance(el, basestring):
for sub in flatten(el):
yield sub
else:
yield el
``````

I used the Iterable ABC added in 2.6.

## Python 3

In Python 3, the `basestring` is no more, but you can use a tuple of `str` and `bytes` to get the same effect there.

The `yield from` operator returns an item from a generator one at a time. This syntax for delegating to a subgenerator was added in 3.3

``````from collections.abc import Iterable

def flatten(l):
for el in l:
if isinstance(el, Iterable) and not isinstance(el, (str, bytes)):
yield from flatten(el)
else:
yield el``````

My solution:

``````import collections

def flatten(x):
if isinstance(x, collections.Iterable):
return [a for i in x for a in flatten(i)]
else:
return [x]
``````

A little more concise, but pretty much the same.

Generator using recursion and duck typing (updated for Python 3):

``````def flatten(L):
for item in L:
try:
yield from flatten(item)
except TypeError:
yield item

list(flatten([[[1, 2, 3], [4, 5]], 6]))
>>>[1, 2, 3, 4, 5, 6]``````

Here is my functional version of recursive flatten which handles both tuples and lists, and lets you throw in any mix of positional arguments. Returns a generator which produces the entire sequence in order, arg by arg:

``````flatten = lambda *n: (e for a in n
for e in (flatten(*a) if isinstance(a, (tuple, list)) else (a,)))
``````

Usage:

``````l1 = ['a', ['b', ('c', 'd')]]
l2 = [0, 1, (2, 3), [[4, 5, (6, 7, (8,), [9]), 10]], (11,)]
print list(flatten(l1, -2, -1, l2))
['a', 'b', 'c', 'd', -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]``````

Generator version of @unutbu’s non-recursive solution, as requested by @Andrew in a comment:

``````def genflat(l, ltypes=collections.Sequence):
l = list(l)
i = 0
while i < len(l):
while isinstance(l[i], ltypes):
if not l[i]:
l.pop(i)
i -= 1
break
else:
l[i:i + 1] = l[i]
yield l[i]
i += 1
``````

Slightly simplified version of this generator:

``````def genflat(l, ltypes=collections.Sequence):
l = list(l)
while l:
while l and isinstance(l[0], ltypes):
l[0:1] = l[0]
if l: yield l.pop(0)``````

This version of `flatten` avoids python’s recursion limit (and thus works with arbitrarily deep, nested iterables). It is a generator which can handle strings and arbitrary iterables (even infinite ones).

``````import itertools as IT
import collections

def flatten(iterable, ltypes=collections.Iterable):
remainder = iter(iterable)
while True:
first = next(remainder)
if isinstance(first, ltypes) and not isinstance(first, (str, bytes)):
remainder = IT.chain(first, remainder)
else:
yield first
``````

Here are some examples demonstrating its use:

``````print(list(IT.islice(flatten(IT.repeat(1)),10)))
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

print(list(IT.islice(flatten(IT.chain(IT.repeat(2,3),
{10,20,30},
'foo bar'.split(),
IT.repeat(1),)),10)))
# [2, 2, 2, 10, 20, 30, 'foo', 'bar', 1, 1]

print(list(flatten([[1,2,[3,4]]])))
# [1, 2, 3, 4]

seq = ([[chr(i),chr(i-32)] for i in range(ord('a'), ord('z')+1)] + list(range(0,9)))
print(list(flatten(seq)))
# ['a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F', 'g', 'G', 'h', 'H',
# 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p', 'P',
# 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X',
# 'y', 'Y', 'z', 'Z', 0, 1, 2, 3, 4, 5, 6, 7, 8]
``````

Although `flatten` can handle infinite generators, it can not handle infinite nesting:

``````def infinitely_nested():
while True:
yield IT.chain(infinitely_nested(), IT.repeat(1))

print(list(IT.islice(flatten(infinitely_nested()), 10)))
# hangs``````

Here’s another answer that is even more interesting…

``````import re

def Flatten(TheList):
a = str(TheList)
b,_Anon = re.subn(r'[\[,\]]', ' ', a)
c = b.split()
d = [int(x) for x in c]

return(d)
``````

Basically, it converts the nested list to a string, uses a regex to strip out the nested syntax, and then converts the result back to a (flattened) list.

## How to flatten an irregular list of lists in Python? Answer #8:

It was fun trying to create a function that could flatten irregular list in Python, but of course that is what Python is for (to make programming fun). The following generator works fairly well with some caveats:

``````def flatten(iterable):
try:
for item in iterable:
yield from flatten(item)
except TypeError:
yield iterable
``````

It will flatten datatypes that you might want left alone (like `bytearray``bytes`, and `str` objects). Also, the code relies on the fact that requesting an iterator from a non-iterable raises a `TypeError`.

``````>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> def flatten(iterable):
try:
for item in iterable:
yield from flatten(item)
except TypeError:
yield iterable

>>> list(flatten(L))
[1, 2, 3, 4, 5, 6]
>>>
``````

Edit:

I disagree with the previous implementation. The problem is that you should not be able to flatten something that is not an iterable. It is confusing and gives the wrong impression of the argument.

``````>>> list(flatten(123))
[123]
>>>
``````

The following generator is almost the same as the first but does not have the problem of trying to flatten a non-iterable object. It fails as one would expect when an inappropriate argument is given to it.

``````def flatten(iterable):
for item in iterable:
try:
yield from flatten(item)
except TypeError:
yield item
``````

Testing the generator works fine with the list that was provided. However, the new code will raise a `TypeError` when a non-iterable object is given to it. Example are shown below of the new behavior.

``````>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> list(flatten(L))
[1, 2, 3, 4, 5, 6]
>>> list(flatten(123))
Traceback (most recent call last):
File "<pyshell#32>", line 1, in <module>
list(flatten(123))
File "<pyshell#27>", line 2, in flatten
for item in iterable:
TypeError: 'int' object is not iterable
>>>``````

Hope you learned something from this post.