How to optimally turn a multidimentional list into a single list of items in Python?

Question

Possible Duplicates:
Making a flat list out of list of lists in Python
Flatten (an irregular) list of lists in Python

Input a list such as: [1,2,[3,4,[5,6,7,[8]]],[9],10]

Desired output: [1,2,3,4,5,6,7,8,9,10]

Currently I have the following recursive function:

def fix_list( li , l = [] ):
    for i in li:
        try:
            len( i )
            fix_list( i, l )
        except:
            l.append( i )
    return l

I feel like the try/except catch is a little gimmicky and slow, and I'm wondering if there is a better/more optimized way to perform this task. All input is greatly appreciated.

See here: http://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists-in-python — phant0m, Jul 13 '11 at 12:58
It is very easy once you figure it out to see how slow (or not) your function is with the timeit module. — Trufa, Jul 13 '11 at 13:02
I like this question because the answers illustrate a good use of generators rather than returning a whole new list. — phkahler, Jul 13 '11 at 13:42

kindall · Answer 1 · 2011-07-14T20:29:19.133

Here is an iterative version (originally inspired by Artsiom Rudzenka's) that modifies the list in place using slice assignment rather than creating a new list on each pass. Interestingly, only one pass through the list is needed! My use of enumerate() is a little unorthodox; I use it to keep track of an index into a list that may be growing as I iterate over it, but don't actually use the actual list item.

def flattened(items, seqtypes=(list, tuple)):

    items = items[:]  # we will return a copy; remove to mutate original
    for i, _ in enumerate(items):
        while isinstance(items[i], seqtypes):
            items[i:i+1] = items[i]
    return items

print flattened([1,2,[3,4,[5,6,7,[8]]],[9],10])

Generator version:

def flattener(items, seqtypes=(list, tuple)):

    items = items[:]
    for i, _ in enumerate(items):
        while isinstance(items[i], seqtypes):
            items[i:i+1] = items[i]
        yield items[i]

print list(flattener([1,2,[3,4,[5,6,7,[8]]],[9],10]))

Here is a list subclass that has a flatten() method. Like the sort() and reverse() methods, this mutates the list and returns None.

class listy(list):

    def flatten(self, seqtypes=(list, tuple)):
        for i, _ in enumerate(self):
            while isinstance(self[i], seqtypes):
                self[i:i+1] = self[i]

lst = listy([1,2,[3,4,[5,6,7,[8]]],[9],10])
lst.flatten()
print lst

Edit: I simplified this pretty significantly from my original version. However, I see the question has been closed.

score 1 · Answer 2 · edited May 23 '17 at 12:27

1

See this answer:

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

edited May 23 '17 at 12:27

Community

1
1

answered Jul 13 '11 at 12:59

orlp

112,504
36
218
315

@Gandi: Well at least I said where I got it, senderle didn't. – orlp Jul 13 '11 at 13:01
I don't say there's anything wrong in it. – Gandi Jul 13 '11 at 13:03
That doesn't mean you should post it as an aswer IMHO; but rather note that it is a duplicate of another question. – phant0m Jul 13 '11 at 13:04
@nightcracker, I wrote it in the process of trying to understand how to create a recursive generator :). Eerily similar, though, isn't it? – senderle Jul 13 '11 at 13:04

score 1 · Answer 3 · answered Jul 13 '11 at 12:59

1

Here's a simple generator that does this:

def flatten(nested):
    for item in nested:
        if isinstance(item, collections.Iterable) and not isinstance(item, basestring):
            for inner_item in flatten(item):
                yield inner_item
        else:
            yield item

Not sure whether it's "optimal" or not.

answered Jul 13 '11 at 12:59

senderle

145,869
36
209
233

Did you just copy that solution and rename variables so its your own? – phant0m Jul 13 '11 at 13:03
@phant0m, no, I copied it from a script that I wrote a while ago trying to understand recursive generators. I'm unsettled by its similarity to the one nightcracker posted though. – senderle Jul 13 '11 at 13:12
Mine looks exactly the same, except when checking for an iterable I use hasattr(el, '\_\_iter\_\_'). The rest is practically identical. Anyone spending 15 minutes on this will come to more or less the same solution. – pi. Jul 13 '11 at 13:32

Artsiom Rudzenka · Answer 4 · 2011-07-13T15:54:45.510

1

I have tried solution below and it works:

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

while any(isinstance(x, list) for x in data):
    tmpLst = []
    for x in data:
        if isinstance(x, list):
            tmpLst.extend(x)
        else:
            tmpLst.append(x)
    data = tmpLst

edited Jul 13 '11 at 15:54

answered Jul 13 '11 at 13:21

Artsiom Rudzenka

27,895
4
34
52

Why make a copy of `tmpLst` at the end of the loop? – kindall Jul 13 '11 at 15:13
@kindall - i am modifying initial list in order to have ability to leave while loop. – Artsiom Rudzenka Jul 13 '11 at 15:25
yes, but it seems to me that `data = tmpLst` would work fine, without using the slice/copy, since `tmpLst` is already a copy of the original list. – kindall Jul 13 '11 at 15:47
Have tried it and yes - seems that you are right(i simply use it with [:] in order to not get an error with shallow/deep copy). – Artsiom Rudzenka Jul 13 '11 at 15:54

Justin · Answer 5 · 2011-07-13T17:41:43.837

Another approach ..

def flatten(old, new):                                                                                                                      
    for i in old:                                                                                                                           
        flatten(i, new) if isinstance(i, list) else new.append(i)                                                                           
    return new                                                                                                                              

if __name__ == '__main__':                                                                                                                  
    l1 = [1, 2, [3, 4, [5, 6, 7, [8]]], [9], 10]                                                                                            
    l2 = list()                                                                                                                             
    l3 = flatten(l1, l2)                                                                                                                     
    print l3

Simplified so you don't have to supply and empty list to the flatten argument list ..

def rec_flatten(old, new=list()):                                                                                                           
    for i in old:                                                                                                                           
        rec_flatten(i, new) if isinstance(i, list) else new.append(i)                                                                       
    return new                                                                                                                              

if __name__ == '__main__':                                                                                                                  
    l1 = [1, 2, [3, 4, [5, 6, 7, [8]]], [9], 10]                                                                                            
    x = rec_flatten(l1)                                                                                                                     
    print x

Your second version will accumulate multiple lists; try calling it a few times in a single script. — kindall, Jul 14 '11 at 04:26

How to optimally turn a multidimentional list into a single list of items in Python?

5 Answers5

Linked