Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   Flattening lists (http://www.velocityreviews.com/forums/t668999-flattening-lists.html)

 mk 02-05-2009 01:17 PM

Flattening lists

Hello everybody,

Any better solution than this?

def flatten(x):
res = []
for el in x:
if isinstance(el,list):
res.extend(flatten(el))
else:
res.append(el)
return res

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

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

Regards,
mk

 Mark Dickinson 02-05-2009 03:21 PM

Re: Flattening lists

On Feb 5, 1:17*pm, mk <mrk...@gmail.com> wrote:
> Hello everybody,
>
> Any better solution than this?
>
> def flatten(x):

Just out of interest, how often do people really need
such a recursive flatten, as opposed to a single-level
version?

I often find myself needing a 'concat' method that
turns a list of lists (or iterable of iterables) into
a single list; itertools.chain does this quite nicely.
But I don't think I've ever encountered a need for the
full recursive version.

Mark

 Michele Simionato 02-05-2009 03:33 PM

Re: Flattening lists

On Feb 5, 2:17*pm, mk <mrk...@gmail.com> wrote:
> Hello everybody,
>
> Any better solution than this?
>
> def flatten(x):
> * * *res = []
> * * *for el in x:
> * * * * *if isinstance(el,list):
> * * * * * * *res.extend(flatten(el))
> * * * * *else:
> * * * * * * *res.append(el)
> * * *return res
>
> a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]]
> print flatten(a)
>
> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>
> Regards,
> mk

Looks fine to me. In some situations you may also use hasattr(el,
'__iter__') instead of isinstance(el, list) (it depends if you want to
flatten generic iterables or only lists).

 mk 02-05-2009 04:06 PM

Re: Flattening lists

Mark Dickinson wrote:
> I often find myself needing a 'concat' method that
> turns a list of lists (or iterable of iterables) into
> a single list; itertools.chain does this quite nicely.
> But I don't think I've ever encountered a need for the
> full recursive version.

You're most probably right in this; however, my main goal here was
finding 'more Pythonic' way of doing this and learning this way rather
than the practical purpose of flattening deeply nested lists.

Regards,
mk

 mk 02-05-2009 04:07 PM

Re: Flattening lists

Michele Simionato wrote:

> Looks fine to me. In some situations you may also use hasattr(el,
> '__iter__') instead of isinstance(el, list) (it depends if you want to
> flatten generic iterables or only lists).

Thanks! Such stuff is what I'm looking for.

Regards,
mk

 J Kenneth King 02-05-2009 04:45 PM

Re: Flattening lists

mk <mrkafk@gmail.com> writes:

> Hello everybody,
>
> Any better solution than this?
>
> def flatten(x):
> res = []
> for el in x:
> if isinstance(el,list):
> res.extend(flatten(el))
> else:
> res.append(el)
> return res
>
> a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]]
> print flatten(a)
>
>
> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>
> Regards,
> mk

http://mail.python.org/pipermail/pyt...ly/330367.html

 Aahz 02-05-2009 06:24 PM

Re: Flattening lists

Michele Simionato <michele.simionato@gmail.com> wrote:
>
>Looks fine to me. In some situations you may also use hasattr(el,
>'__iter__') instead of isinstance(el, list) (it depends if you want to
>flatten generic iterables or only lists).

Of course, once you do that, you need to special-case strings...
--
Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/

Weinberg's Second Law: If builders built buildings the way programmers wrote
programs, then the first woodpecker that came along would destroy civilization.

 Tobiah 02-05-2009 07:06 PM

Re: Flattening lists

> Hello everybody,
>
> Any better solution than this?

a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]]
print str(a).replace('[', '').replace(']', '').split(', ')

;)

 rdmurray@bitdance.com 02-05-2009 07:07 PM

Re: Flattening lists

Quoth J Kenneth King <james@agentultra.com>:
> mk <mrkafk@gmail.com> writes:
>
> > Hello everybody,
> >
> > Any better solution than this?
> >
> > def flatten(x):
> > res = []
> > for el in x:
> > if isinstance(el,list):
> > res.extend(flatten(el))
> > else:
> > res.append(el)
> > return res
> >
> > a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]]
> > print flatten(a)
> >
> >
> > [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
> >
> > Regards,
> > mk

>
> http://mail.python.org/pipermail/pyt...ly/330367.html

That's worth reading. I'm not sure why I'm finding this fun, but who
cares. I tried a couple of other functions after reading that article,
and it looks like a generator that scans the nested lists is actually
the winner, and also is in many ways the most elegant implementation.
Of course, as noted in the emails following above article, the test data
is really inadequate for proper optimization testing ;)

-----------------------------------------------------------------
from __future__ import print_function
from timeit import Timer
from itertools import chain

# This is the one from the article quoted above.
def flatten6(seq):
i = 0
while (i != len(seq)):
while hasattr(seq[i], '__iter__'):
seq[i:i+1] = seq[i]
i = i + 1
return seq

#This is my favorite from a readability standpoint out of
#all the things I tried. It also performs the best.
def flatten8(seq):
for x in seq:
if not hasattr(x, '__iter__'): yield x
else:
for y in flatten8(x):
yield y

l = [[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [[[[[5, 4], 3], 4, 3], 3, 1, 45], 9], 10]]

if __name__=="__main__":
print(l)
print('flatten6', flatten6(l))
print('flatten8', list(flatten8(l)))
print('flatten6', Timer("flatten6(l)", "from temp3 import flatten6, l").timeit())
print('flatten8', Timer("list(flatten8(l))", "from temp3 import flatten8, l").timeit())

-----------------------------------------------------------------

>src/python/Python-3.0/python temp3.py

[[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [[[[[5, 4], 3], 4, 3], 3, 1, 45], 9], 10]]
flatten6 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10]
flatten8 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10]
flatten6 32.8386368752
flatten8 30.7509689331

>python temp3.py

[[1, 2, 3], 5, [7, 8], 3, [9, [10, 11, 12], 4, [9, [10, 5, 7]], 1, [[[[[5, 4], 3], 4, 3], 3, 1, 45], 9], 10]]
flatten6 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10]
flatten8 [1, 2, 3, 5, 7, 8, 3, 9, 10, 11, 12, 4, 9, 10, 5, 7, 1, 5, 4, 3, 4, 3, 3, 1, 45, 9, 10]
flatten6 34.730714798
flatten8 32.3252940178

--RDM

 Tobiah 02-05-2009 07:13 PM

Re: Flattening lists

On Thu, 05 Feb 2009 11:06:39 -0800, Tobiah wrote:

>
>> Hello everybody,
>>
>> Any better solution than this?

>
> a = [1, 2, 3, [4, 5, 6], [[7, 8], [9, 10]]] print str(a).replace('[',
> '').replace(']', '').split(', ')
>
> ;)

Or:

a = ['text', 'string', 3, [4, 5, 6], [[7, 8], [9, 10]]]
print eval("[" + str(a).replace('[', '').replace(']', '') + "]")

Just tongue in cheek...

All times are GMT. The time now is 06:32 AM.