By telliott99


2010-01-28 22:15:42 8 Comments

Yes, I know this subject has been covered before (here, here, here, here), 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 found in this question:

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?

30 comments

@ADR 2019-03-22 18:00:27

Just use a funcy library: pip install funcy

import funcy


funcy.flatten([[[[1, 1], 1], 2], 3]) # returns generator
funcy.lflatten([[[[1, 1], 1], 2], 3]) # returns list

@Jorge Orpinel 2019-01-22 10:22:40

No recursion or nested loops. A few lines. Well formatted and easy to read:

def flatten_deep(arr: list):
""" Flattens arbitrarily-nested list `arr` into single-dimensional. """

while arr:
    if isinstance(arr[0], list):  # Checks whether first element is a list
        arr = arr[0] + arr[1:]  # If so, flattens that first element one level
    else:
        yield arr.pop(0)  # Otherwise yield as part of the flat array

flatten_deep(L)

From my own code at https://github.com/jorgeorpinel/flatten_nested_lists/blob/master/flatten.py

@Statham 2018-11-28 15:48:09

This is a simple implement of flatten on python2

flatten=lambda l: reduce(lambda x,y:x+y,map(flatten,l),[]) if isinstance(l,list) else [l]

test=[[1,2,3,[3,4,5],[6,7,[8,9,[10,[11,[12,13,14]]]]]],]
print flatten(test)

#output [1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

@whackamadoodle3000 2017-08-09 17:42:53

Similar to diligar's answer

weird_list=[[1, 2, 3], [4, 5, 6], [7], [8, 9]]
nice_list = list(map(int, ''.join([e for e in str(weird_list) if e not in '[ ]']).split(',')))

@cglacet 2018-08-02 09:02:19

When trying to answer such a question you really need to give the limitations of the code you propose as a solution. If it was only about performances I wouldn't mind too much, but most of the codes proposed as solution (including the accepted answer) fail to flatten any list that has a depth greater than 1000.

When I say most of the codes I mean all codes that use any form of recursion (or call a standard library function that is recursive). All these codes fail because for every of the recursive call made, the (call) stack grow by one unit, and the (default) python call stack has a size of 1000.

If you're not too familiar with the call stack, then maybe the following will help (otherwise you can just scroll to the Implementation).

Call stack size and recursive programming (dungeon analogy)

Finding the treasure and exit

Imagine you enter a huge dungeon with numbered rooms, looking for a treasure. You don't know the place but you have some indications on how to find the treasure. Each indication is a riddle (difficulty varies, but you can't predict how hard they will be). You decide to think a little bit about a strategy to save time, you make two observations:

  1. It's hard (long) to find the treasure as you'll have to solve (potentially hard) riddles to get there.
  2. Once the treasure found, returning to the entrance may be easy, you just have to use the same path in the other direction (though this needs a bit of memory to recall your path).

When entering the dungeon, you notice a small notebook here. You decide to use it to write down every room you exit after solving a riddle (when entering a new room), this way you'll be able to return back to the entrance. That's a genius idea, you won't even spend a cent implementing your strategy.

You enter the dungeon, solving with great success the first 1001 riddles, but here comes something you hadn't planed, you have no space left in the notebook you borrowed. You decide to abandon your quest as you prefer not having the treasure than being lost forever inside the dungeon (that looks smart indeed).

Executing a recursive program

Basically, it's the exact same thing as finding the treasure. The dungeon is the computer's memory, your goal now is not to find a treasure but to compute some function (find f(x) for a given x). The indications simply are sub-routines that will help you solving f(x). Your strategy is the same as the call stack strategy, the notebook is the stack, the rooms are the functions' return addresses:

x = ["over here", "am", "I"]
y = sorted(x) # You're about to enter a room named `sorted`, note down the current room address here so you can return back: 0x4004f4 (that room address looks weird)
# Seems like you went back from your quest using the return address 0x4004f4
# Let's see what you've collected 
print(' '.join(y))

The problem you encountered in the dungeon will be the same here, the call stack has a finite size (here 1000) and therefore, if you enter too many functions without returning back then you'll fill the call stack and have an error that look like "Dear adventurer, I'm very sorry but your notebook is full": RecursionError: maximum recursion depth exceeded. Note that you don't need recursion to fill the call stack, but it's very unlikely that a non-recursive program call 1000 functions without ever returning. It's important to also understand that once you returned from a function, the call stack is freed from the address used (hence the name "stack", return address are pushed in before entering a function and pulled out when returning). In the special case of a simple recursion (a function f that call itself once -- over and over --) you will enter f over and over until the computation is finished (until the treasure is found) and return from f until you go back to the place where you called f in the first place. The call stack will never be freed from anything until the end where it will be freed from all return addresses one after the other.

How to avoid this issue?

That's actually pretty simple: "don't use recursion if you don't know how deep it can go". That's not always true as in some cases, Tail Call recursion can be Optimized (TCO). But in python, this is not the case, and even "well written" recursive function will not optimize stack use. There is an interesting post from Guido about this question: Tail Recursion Elimination.

There is a technique that you can use to make any recursive function iterative, this technique we could call bring your own notebook. For example, in our particular case we simply are exploring a list, entering a room is equivalent to entering a sublist, the question you should ask yourself is how can I get back from a list to its parent list? The answer is not that complex, repeat the following until the stack is empty:

  1. push the current list address and index in a stack when entering a new sublist (note that a list address+index is also an address, therefore we just use the exact same technique used by the call stack);
  2. every time an item is found, yield it (or add them in a list);
  3. once a list is fully explored, go back to the parent list using the stack return address (and index).

Also note that this is equivalent to a DFS in a tree where some nodes are sublists A = [1, 2] and some are simple items: 0, 1, 2, 3, 4 (for L = [0, [1,2], 3, 4]). The tree looks like this:

                    L
                    |
           -------------------
           |     |     |     |
           0   --A--   3     4
               |   |
               1   2

The DFS traversal pre-order is: L, 0, A, 1, 2, 3, 4. Remember, in order to implement an iterative DFS you also "need" a stack. The implementation I proposed before result in having the following states (for the stack and the flat_list):

init.:  stack=[(L, 0)]
**0**:  stack=[(L, 0)],         flat_list=[0]
**A**:  stack=[(L, 1), (A, 0)], flat_list=[0]
**1**:  stack=[(L, 1), (A, 0)], flat_list=[0, 1]
**2**:  stack=[(L, 1), (A, 1)], flat_list=[0, 1, 2]
**3**:  stack=[(L, 2)],         flat_list=[0, 1, 2, 3]
**3**:  stack=[(L, 3)],         flat_list=[0, 1, 2, 3, 4]
return: stack=[],               flat_list=[0, 1, 2, 3, 4]

In this example, the stack maximum size is 2, because the input list (and therefore the tree) have depth 2.

Implementation

For the implementation, in python you can simplify a little bit by using iterators instead of simple lists. References to the (sub)iterators will be used to store sublists return addresses (instead of having both the list address and the index). This is not a big difference but I feel this is more readable (and also a bit faster):

def flatten(iterable):
    return list(items_from(iterable))

def items_from(iterable):
    cursor_stack = [iter(iterable)]
    while cursor_stack:
        sub_iterable = cursor_stack[-1]
        try:
            item = next(sub_iterable)
        except StopIteration:   # post-order
            cursor_stack.pop()
            continue
        if is_list_like(item):  # pre-order
            cursor_stack.append(iter(item))
        elif item is not None:
            yield item          # in-order

def is_list_like(item):
    return isinstance(item, list)

Also, notice that in is_list_like I have isinstance(item, list), which could be changed to handle more input types, here I just wanted to have the simplest version where (iterable) is just a list. But you could also do that:

def is_list_like(item):
    try:
        iter(item)
        return not isinstance(item, str)  # strings are not lists (hmm...) 
    except TypeError:
        return False

This considers strings as "simple items" and therefore flatten_iter([["test", "a"], "b]) will return ["test", "a", "b"] and not ["t", "e", "s", "t", "a", "b"]. Remark that in that case, iter(item) is called twice on each item, let's pretend it's an exercise for the reader to make this cleaner.

Testing and remarks on other implementations

In the end, remember that you can't print a infinitely nested list L using print(L) because internally it will use recursive calls to __repr__ (RecursionError: maximum recursion depth exceeded while getting the repr of an object). For the same reason, solutions to flatten involving str will fail with the same error message.

If you need to test your solution, you can use this function to generate a simple nested list:

def build_deep_list(depth):
    """Returns a list of the form $l_{depth} = [depth-1, l_{depth-1}]$
    with $depth > 1$ and $l_0 = [0]$.
    """
    sub_list = [0]
    for d in range(1, depth):
        sub_list = [d, sub_list]
    return sub_list

Which gives: build_deep_list(5) >>> [4, [3, [2, [1, [0]]]]].

@Emilio M Bumachar 2018-03-23 18:23:53

def flatten(nestedList):
    return eval('['+str(nestedList).replace('[','').replace(']','')+']')

Turns the nested list into a string, removes the brackets, then adds just two brackets around it and evaluates.

Will work if all leaf elements are integers.

Will not work if leaf elements are arbitrary strings (which might contain brackets).

Needs to be evaluated on a case-by-case bases on whether it will work for other cases.

Does not use regex, unlike the other answer that involves turning the list into a string.

Hacky, and expected to be slow, but I don't think it can be beaten on readability.

@wihlke 2018-01-15 15:25:30

From my previous answer, this function flattens most cases I can think of. I believe this works down to python 2.3.

def flatten(item, keepcls=(), keepobj=()):
    if not hasattr(item, '__iter__') or isinstance(item, keepcls) or item in keepobj:
        yield item
    else:
        for i in item:
            for j in flatten(i, keepcls, keepobj + (item,)):
                yield j

Circular lists

>>> list(flatten([1, 2, [...], 3]))
[1, 2, [1, 2, [...], 3], 3]

Depth first lists

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

Nested repeated lists:

>>> list(flatten([[1,2],[1,[1,2]],[1,2]]))
[1, 2, 1, 1, 2, 1, 2]

Lists with dicts (or other objects to not flatten)

>>> list(flatten([1,2, {'a':1, 'b':2}, 'text'], keepcls=(dict, str)))
[1, 2, {'a': 1, 'b': 2}, 'text']

Any iterables

>>> list(flatten((x for x in [1,2, set([3,(4,5),6])])))
[1, 2, 4, 5, 3, 6]

You may want to keep some default classes in keepcls to make calling the function more terse.

@Shivpe_R 2017-11-22 12:26:03

Simple Function Without using instances

L = [[[1, 2, 3], [4, 5]], 6]
l1 = []
def FlattenList(List1):
    for i in range(len(List1)):
        if type(List1[i]) == type([]):
            FlattenList(List1[i])
        else:
            l1.append(List1[i])
    return l1


FlattenList(L)
[1, 2, 3, 4, 5, 6]

@Fuji Komalan 2017-02-27 16:01:25

Python-3

from collections import Iterable

L = [[[1, 2, 3], [4, 5]], 6,[7,[8,9,[10]]]]

def flatten(thing):
    result = []

    if isinstance(thing, Iterable):
        for item in thing:
            result.extend(flatten(item))
    else:
        result.append(thing)

    return result


flat = flatten(L)
print(flat)

@MSeifert 2017-07-29 14:01:42

You could use deepflatten from the 3rd party package iteration_utilities:

>>> from iteration_utilities import deepflatten
>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> list(deepflatten(L))
[1, 2, 3, 4, 5, 6]

>>> list(deepflatten(L, types=list))  # only flatten "inner" lists
[1, 2, 3, 4, 5, 6]

It's an iterator so you need to iterate it (for example by wrapping it with list or using it in a loop). Internally it uses an iterative approach instead of an recursive approach and it's written as C extension so it can be faster than pure python approaches:

>>> %timeit list(deepflatten(L))
12.6 µs ± 298 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> %timeit list(deepflatten(L, types=list))
8.7 µs ± 139 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

>>> %timeit list(flatten(L))   # Cristian - Python 3.x approach from https://stackoverflow.com/a/2158532/5393381
86.4 µs ± 4.42 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

>>> %timeit list(flatten(L))   # Josh Lee - https://stackoverflow.com/a/2158522/5393381
107 µs ± 2.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

>>> %timeit list(genflat(L, list))  # Alex Martelli - https://stackoverflow.com/a/2159079/5393381
23.1 µs ± 710 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

I'm the author of the iteration_utilities library.

@Edityouprofile 2017-10-18 04:12:01

I wonder why this package has caused so less attention...

@MSeifert 2017-10-18 10:55:21

@displayname There are several (lots) of libraries that provide such tools or similar ones: more-itertools, toolz, ... that have been around for much longer. They just differ a bit in available functionality/speed/options but they overlap in many respects. iteration_utilities is quite new and the only "advantage" is that it's faster in some cases than the alternatives. So it's really not surprising that it doesn't get much attention.

@Edityouprofile 2017-10-19 02:53:25

I tried and thanks for the great package. It's super fast!

@DeaD_EyE 2017-07-20 11:42:27

Iterative solution with Python 3

This solution may work with all objects except str and bytes.

from collections import Iterable
from collections import Iterator


def flat_iter(obj):
    stack = [obj]
    while stack:
        element = stack.pop()
        if element and isinstance(element, Iterator):
            stack.append(element)
            try:
                stack.append(next(element))
            except StopIteration:
                stack.pop()
        elif isinstance(element, Iterable) and not isinstance(element, (str, bytes)):
            stack.append(iter(element))
        else:
            yield element


tree_list = [[(1,2,3),(4,5,6, (7,8, 'next element is 5')), (5,6), [[[3,4,5],'foo1'],'foo2'],'foo3']]

not_iterable = 10

it1 = flat_iter(tree_list)
it2 = flat_iter(not_iterable)

print(list(it1))
print(list(it2))

[1, 2, 3, 4, 5, 6, 7, 8, 'next element is 5', 5, 6, 3, 4, 5, 'foo1', 'foo2', 'foo3']

[10]

@diligar 2017-05-13 02:32:08

I'm not sure if this is necessarily quicker or more effective, but this is what I do:

def flatten(lst):
    return eval('[' + str(lst).replace('[', '').replace(']', '') + ']')

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

The flatten function here turns the list into a string, takes out all of the square brackets, attaches square brackets back onto the ends, and turns it back into a list.

Although, if you knew you would have square brackets in your list in strings, like [[1, 2], "[3, 4] and [5]"], you would have to do something else.

@cglacet 2018-08-02 06:47:05

This has no advantage over the simple solution as this fails to process deep lists, ie "RecursionError: maximum recursion depth exceeded while getting the repr of an object".

@Matt Farguson 2017-02-27 01:28:19

This will flatten a list or dictionary (or list of lists or dictionaries of dictionaries etc). It assumes that the values are strings and it creates a string that concatenates each item with a separator argument. If you wanted you could use the separator to split the result into a list object afterward. It uses recursion if the next value is a list or a string. Use the key argument to tell whether you want the keys or the values (set key to false) from the dictionary object.

def flatten_obj(n_obj, key=True, my_sep=''):
    my_string = ''
    if type(n_obj) == list:
        for val in n_obj:
            my_sep_setter = my_sep if my_string != '' else ''
            if type(val) == list or type(val) == dict:
                my_string += my_sep_setter + flatten_obj(val, key, my_sep)
            else:
                my_string += my_sep_setter + val
    elif type(n_obj) == dict:
        for k, v in n_obj.items():
            my_sep_setter = my_sep if my_string != '' else ''
            d_val = k if key else v
            if type(v) == list or type(v) == dict:
                my_string += my_sep_setter + flatten_obj(v, key, my_sep)
            else:
                my_string += my_sep_setter + d_val
    elif type(n_obj) == str:
        my_sep_setter = my_sep if my_string != '' else ''
        my_string += my_sep_setter + n_obj
        return my_string
    return my_string

print(flatten_obj(['just', 'a', ['test', 'to', 'try'], 'right', 'now', ['or', 'later', 'today'],
                [{'dictionary_test': 'test'}, {'dictionary_test_two': 'later_today'}, 'my power is 9000']], my_sep=', ')

yields:

just, a, test, to, try, right, now, or, later, today, dictionary_test, dictionary_test_two, my power is 9000

@Leo wahyd 2016-10-03 15:46:27

I am aware that there are already many awesome answers but i wanted to add an answer that uses the functional programming method of solving the question. In this answer i make use of double recursion :

def flatten_list(seq):
    if not seq:
        return []
    elif isinstance(seq[0],list):
        return (flatten_list(seq[0])+flatten_list(seq[1:]))
    else:
        return [seq[0]]+flatten_list(seq[1:])

print(flatten_list([1,2,[3,[4],5],[6,7]]))

output:

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

@Cristian 2010-01-28 22:35:51

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

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

@telliott99 2010-01-29 00:04:04

I like that this is a generator, and very clear. Adding a guard against having a string in the list (not in the original spec, but will definitely blow the recursion limit), would make it perfect.

@Cristian 2010-01-29 00:24:10

You're right. I added a string check.

@nemesisfixx 2012-06-07 15:04:35

Of all the suggestions on this page, this is the only one that flattened this list l = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9)) in a snap when i did this list(flatten(l)). All the others, would start working and take forever!

@2rs2ts 2013-05-31 23:33:02

This flattened my tuple of strings and lists containing strings that I was using as *args in a function I wrote... thank you!

@devsaw 2013-12-23 09:39:15

AN elegant solution .even I posted a similar one in one of those questions stated by the OP

@Bakuriu 2014-04-27 20:28:49

Can be further simplified in python3.3+ using yield from flatten(el) instead of that loop.

@ChillarAnand 2014-12-23 04:08:54

If you are using py3, use str insteadof basestring

@josch 2015-06-21 12:37:40

This also flattens dictionaries. Maybe you want to use collections.Sequence instead of collections.Iteratable?

@RolKau 2015-08-18 11:17:41

This doesn't work with things that aren't lists initially, e.g. for i in flatten(42): print (i). This could be fixed by moving the isinstance-test and the else-clause outside of the for el-loop. (Then you could throw anything at it, and it would make a flattened list out of it)

@yelsayed 2016-05-09 04:41:13

Why do you need the compound check if isinstance(el, collections.Iterable) and not isinstance(el, basestring)? Why not just if not isinstance(el, list)?

@dawg 2018-09-30 15:53:47

For Python 3.7, using collections.Iterable is deprecated. Use collections.abc.Iterable instead.

@jorijnsmit 2018-12-30 09:26:39

@yelsayed because you want to prevent separating strings into their individual letters.

@jorijnsmit 2018-12-30 10:21:45

Put a concise version of this in a Gist for further reference: gist.github.com/jorijnsmit/b6deccd3fd5fefbabb72759c74040745

@Jorge Orpinel 2019-01-22 10:01:11

No recursion needed.

@cglacet 2019-03-11 09:13:22

Indeed, recursion is never needed. In this specific case using recursion is not the best solution as it will crash on deeply nested lists (depth > 1000). But if you don't aim at having something safe, then yes recursive function are better as they are way easier to read/write.

@Shreyas 2016-04-08 13:24:02

I didn't go through all the already available answers here, but here is a one liner I came up with, borrowing from lisp's way of first and rest list processing

def flatten(l): return flatten(l[0]) + (flatten(l[1:]) if len(l) > 1 else []) if type(l) is list else [l]

here is one simple and one not-so-simple case -

>>> flatten([1,[2,3],4])
[1, 2, 3, 4]

>>> flatten([1, [2, 3], 4, [5, [6, {'name': 'some_name', 'age':30}, 7]], [8, 9, [10, [11, [12, [13, {'some', 'set'}, 14, [15, 'some_string'], 16], 17, 18], 19], 20], 21, 22, [23, 24], 25], 26, 27, 28, 29, 30])
[1, 2, 3, 4, 5, 6, {'age': 30, 'name': 'some_name'}, 7, 8, 9, 10, 11, 12, 13, set(['set', 'some']), 14, 15, 'some_string', 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
>>> 

@cs95 2018-01-09 22:44:57

It's not a one liner. No matter how much you attempt to fit it into one, the def foo(): is a separate line. Also, this is very unreadable.

@Emilio M Bumachar 2018-02-05 17:20:40

I've de-one-line-ified the code, and did some further refactoring. (edit is pending peer review as I write this) This particular method seemed very readable to me, though the original code did need some refactoring.

@halcyonjuly7 2016-04-04 20:38:15

this might be an old question i'd like to take a shot at this.

I am a dumb guy so I'll give a "dumb" solution. all that recursion hurts my brain.

flattened_list  = []
nested_list =[[[1, 2, 3], [4, 5]], 6]

def flatten(nested_list, container):
    for item in nested_list:
        if isintance(item, list):
            flatten(item)
        else:
            container.append(i)

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

I get that it's using a side effect but well thats to the best of my comprehension of recursion can go

@noobcoder 2016-03-22 13:55:38

We can also use the 'type' function of python. When iterating the list we check if the item is a list or not. If not we 'append' it else we 'extend' it. Here is a sample code -

l=[1,2,[3,4],5,[6,7,8]]
x=[]
for i in l:
    if type(i) is list:
        x.extend(i)
    else:
        x.append(i)
print x

Output:

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

For more info on append() and extend() check this website : https://docs.python.org/2/tutorial/datastructures.html

@Jorge Orpinel 2019-01-22 10:16:57

Only works for single level nested list.

@YPCrumble 2015-12-15 20:03:50

The easiest way is to use the morph library using pip install morph.

The code is:

import morph

list = [[[1, 2, 3], [4, 5]], 6]
flattened_list = morph.flatten(list)  # returns [1, 2, 3, 4, 5, 6]

@Zion 2015-11-14 05:59:47

I'm surprised no one has thought of this. Damn recursion I don't get the recursive answers that the advanced people here made. anyway here is my attempt on this. caveat is it's very specific to the OP's use case

import re

L = [[[1, 2, 3], [4, 5]], 6]
flattened_list = re.sub("[\[\]]", "", str(L)).replace(" ", "").split(",")
new_list = list(map(int, flattened_list))
print(new_list)

output:

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

@Cong Ma 2015-10-13 22:41:14

Shamelessly taken from my own answer to another question.

This function

  • Does not use isinstance, because it's evil and breaks duck typing.
  • Uses reduce recursively. There has to be an answer using reduce.
  • Works with arbitrary nested-lists whose elements are either nested-lists, or non-nested lists of atoms, or atoms (subjected to recursion limit).
  • Does not LBYL.
  • But not with nested-lists that contain strings as atoms.

Code below:

def flattener(left, right):
    try:
        res = reduce(flattener, right, left)
    except TypeError:
        left.append(right)
        res = left
    return res


def flatten(seq):
    return reduce(flattener, seq, [])


>>> nested_list = [0, [1], [[[[2]]]],
                   [3, [], [4, 5]],
                   [6, [7, 8],
                    9, [[[]], 10,
                        []]],
                   11, [], [],
                   [12]]
>>> flatten(nested_list)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

@dansalmo 2013-01-23 23:04:43

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]

@dansalmo 2015-09-08 14:54:45

Thanks, that works nice for Python 3. For 2.x the previous is needed: for i in flatten(item): yield i

@sten 2018-03-18 23:06:29

list(flatten([['X'], 'Y'])) fails on 2.X variant

@dansalmo 2018-03-20 00:14:03

@user1019129 see my comment above yours

@sten 2018-03-20 20:16:40

yes it fails with the cycle.. i think because a string is also an "array"-of-chars

@arispen 2018-09-14 13:25:40

RecursionError: maximum recursion depth exceeded in compariso :(

@freeyoung 2014-09-30 22:02:25

I used recursive to solve nested list with any depth

def combine_nlist(nlist,init=0,combiner=lambda x,y: x+y):
    '''
    apply function: combiner to a nested list element by element(treated as flatten list)
    '''
    current_value=init
    for each_item in nlist:
        if isinstance(each_item,list):
            current_value =combine_nlist(each_item,current_value,combiner)
        else:
            current_value = combiner(current_value,each_item)
    return current_value

So after i define function combine_nlist, it is easy to use this function do flatting. Or you can combine it into one function. I like my solution because it can be applied to any nested list.

def flatten_nlist(nlist):
    return combine_nlist(nlist,[],lambda x,y:x+[y])

result

In [379]: flatten_nlist([1,2,3,[4,5],[6],[[[7],8],9],10])
Out[379]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

@cglacet 2018-08-01 16:48:46

"nested list with any depth" not true. Just try you'll see: current_value = combiner(current_value,each_item) RecursionError: maximum recursion depth exceeded

@freeyoung 2018-08-01 20:19:55

hmmm I are you trying to flaten list with more than 1000 layers?

@cglacet 2018-08-02 06:44:11

Of course, that's the whole point of the discussion about recursive vs. iterative solutions. If you know in advance that the number of layers is < than 1000 then the most simple solution will work. When you say "any depth" this includes list with depth > 1000.

@Saksham Varma 2015-02-27 02:38:33

Using itertools.chain:

import itertools
from collections import Iterable

def list_flatten(lst):
    flat_lst = []
    for item in itertools.chain(lst):
        if isinstance(item, Iterable):
            item = list_flatten(item)
            flat_lst.extend(item)
        else:
            flat_lst.append(item)
    return flat_lst

Or without chaining:

def flatten(q, final):
    if not q:
        return
    if isinstance(q, list):
        if not isinstance(q[0], list):
            final.append(q[0])
        else:
            flatten(q[0], final)
        flatten(q[1:], final)
    else:
        final.append(q)

@alfasin 2014-12-07 06:06:19

Without using any library:

def flat(l):
    def _flat(l, r):    
        if type(l) is not list:
            r.append(l)
        else:
            for i in l:
                r = r + flat(i)
        return r
    return _flat(l, [])



# example
test = [[1], [[2]], [3], [['a','b','c'] , [['z','x','y']], ['d','f','g']], 4]    
print flat(test) # prints [1, 2, 3, 'a', 'b', 'c', 'z', 'x', 'y', 'd', 'f', 'g', 4]

@Noctis Skytower 2013-07-25 20:46:26

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
>>>

@Samy Vilar 2014-08-17 19:52:51

Here is another py2 approach, Im not sure if its the fastest or the most elegant nor safest ...

from collections import Iterable
from itertools import imap, repeat, chain


def flat(seqs, ignore=(int, long, float, basestring)):
    return repeat(seqs, 1) if any(imap(isinstance, repeat(seqs), ignore)) or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs))

It can ignore any specific (or derived) type you would like, it returns an iterator, so you can convert it to any specific container such as list, tuple, dict or simply consume it in order to reduce memory footprint, for better or worse it can handle initial non-iterable objects such as int ...

Note most of the heavy lifting is done in C, since as far as I know thats how itertools are implemented, so while it is recursive, AFAIK it isn't bounded by python recursion depth since the function calls are happening in C, though this doesn't mean you are bounded by memory, specially in OS X where its stack size has a hard limit as of today (OS X Mavericks) ...

there is a slightly faster approach, but less portable method, only use it if you can assume that the base elements of the input can be explicitly determined otherwise, you'll get an infinite recursion, and OS X with its limited stack size, will throw a segmentation fault fairly quickly ...

def flat(seqs, ignore={int, long, float, str, unicode}):
    return repeat(seqs, 1) if type(seqs) in ignore or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs))

here we are using sets to check for the type so it takes O(1) vs O(number of types) to check whether or not an element should be ignored, though of course any value with derived type of the stated ignored types will fail, this is why its using str, unicode so use it with caution ...

tests:

import random

def test_flat(test_size=2000):
    def increase_depth(value, depth=1):
        for func in xrange(depth):
            value = repeat(value, 1)
        return value

    def random_sub_chaining(nested_values):
        for values in nested_values:
            yield chain((values,), chain.from_iterable(imap(next, repeat(nested_values, random.randint(1, 10)))))

    expected_values = zip(xrange(test_size), imap(str, xrange(test_size)))
    nested_values = random_sub_chaining((increase_depth(value, depth) for depth, value in enumerate(expected_values)))
    assert not any(imap(cmp, chain.from_iterable(expected_values), flat(chain(((),), nested_values, ((),)))))

>>> test_flat()
>>> list(flat([[[1, 2, 3], [4, 5]], 6]))
[1, 2, 3, 4, 5, 6]
>>>  

$ uname -a
Darwin Samys-MacBook-Pro.local 13.3.0 Darwin Kernel Version 13.3.0: Tue Jun  3 21:27:35 PDT 2014; root:xnu-2422.110.17~1/RELEASE_X86_64 x86_64
$ python --version
Python 2.7.5

@Joran Beasley 2014-05-28 17:54:20

totally hacky but I think it would work (depending on your data_type)

flat_list = ast.literal_eval("[%s]"%re.sub("[\[\]]","",str(the_list)))

@unutbu 2010-01-28 22:42:07

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, basestring):
            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 xrange(ord('a'), ord('z')+1)] + 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

@Andrew McGregor 2010-01-28 23:11:34

So the best answer would be to somehow make this a generator.

@wim 2013-09-15 20:09:53

any consensus on whether to use ABC Iterable or ABC Sequence?

@unutbu 2013-09-15 20:16:48

sets, dicts, deques, listiterators, generators, filehandles, and custom classes with __iter__ defined are all instances of collections.Iterable, but not collections.Sequence. The result of flattening a dict is a bit iffy, but otherwise, I think collections.Iterable is a better default than collections.Sequence. It's definitely the more liberal.

@unutbu 2013-09-17 09:27:56

@wim: One problem with using collections.Iterable is that this includes infinite generators. I've changed my answer handle this case.

@Wilfred Hughes 2013-12-10 12:56:51

Here's a simple function that flattens lists of arbitrary depth. No recursion, to avoid stack overflow.

from copy import deepcopy

def flatten_list(nested_list):
    """Flatten an arbitrarily nested list, without recursion (to avoid
    stack overflows). Returns a new list, the original list is unchanged.

    >> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]]))
    [1, 2, 3, 4, 5]
    >> list(flatten_list([[1, 2], 3]))
    [1, 2, 3]

    """
    nested_list = deepcopy(nested_list)

    while nested_list:
        sublist = nested_list.pop(0)

        if isinstance(sublist, list):
            nested_list = sublist + nested_list
        else:
            yield sublist

@Jorge Orpinel 2019-01-22 10:22:27

Related Questions

Sponsored Content

36 Answered Questions

[SOLVED] How do I check if a list is empty?

  • 2008-09-10 06:20:11
  • Ray Vega
  • 2167174 View
  • 3207 Score
  • 36 Answer
  • Tags:   python list

30 Answered Questions

[SOLVED] How do I concatenate two lists in Python?

27 Answered Questions

59 Answered Questions

[SOLVED] How do you split a list into evenly sized chunks?

39 Answered Questions

[SOLVED] How to make a flat list out of list of lists

27 Answered Questions

[SOLVED] How do I list all files of a directory?

  • 2010-07-08 19:31:22
  • duhhunjonn
  • 3132082 View
  • 3429 Score
  • 27 Answer
  • Tags:   python directory

6 Answered Questions

[SOLVED] How do I get the number of elements in a list in Python?

  • 2009-11-11 00:30:54
  • y2k
  • 3050754 View
  • 1762 Score
  • 6 Answer
  • Tags:   python list

29 Answered Questions

[SOLVED] Finding the index of an item given a list containing it in Python

  • 2008-10-07 01:39:38
  • Eugene M
  • 3201822 View
  • 2640 Score
  • 29 Answer
  • Tags:   python list

20 Answered Questions

[SOLVED] How to clone or copy a list?

23 Answered Questions

[SOLVED] Flattening a shallow list in Python

Sponsored Content