Welcome, guest | Sign In | My Account | Store | Cart
0

Function for flattening sequences (currently works on tuples and lists, potentially works on user-defined sequences as well, since it only explicitly disallows strings and dictionaries as sequences). : added a "Thinking . . . " progress measurement of sorts, and a (probably inaccurate) timer.

Python, 46 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46``` ```def flatten(sequence): def hms(fpd): if fpd < 60: return fpd elif fpd < 60**2: return "%s:%s" % (int(fpd/60), fpd-int(fpd/60)*60) else: h = int(fpd/60**2) fpd -= h*60**2 m = int(fpd/60) fpd -= m*60 s = fpd return "%s:%s:%s" % (h, m, s) def rflat(seq2): seq = [] for entry in seq2: if seqin([entry]): seq.extend([i for i in entry]) else: seq.append(entry) return seq def seqin(sequence): for i in sequence: if ('__contains__' in dir(i) and ## all sequences have '__contains__' in their dir() type(i) != str and type(i) != dict): ## parentheses present to aid commenting mid-condition return True return False import time btime = time.time() d1time = btime seq = [sequence][:] ## in case parameter isn't already a sequence print "Thinking", while seqin(seq): d2time = time.time() if d2time-d1time >= 5: print ".", d1time = d2time seq = rflat(seq) atime = time.time() print print "Sequence flattened in " + str(hms(atime-btime)) return seq ```

Extremely useful for highly nested lists, including two-dimensional arrays. For example, if you have a 2d-array to represent the field of a game, flattening it allows easier iteration. There may or may not be an issue with reaching the maximum recursion limit, I'm not an expert on recursion. Either way, however, there are two more implementations you may want to try:

http://aspn.activestate.com/ASPN/Mail/Message/python-tutor/2302348 - recursive-iterator http://aspn.activestate.com/ASPN/Mail/Message/python-tutor/2302231 - NON-RECURSIVE!

jackdied 12 years, 5 months ago

Flatten. I think everyone carries around a version of flatten. Search examples on groups.google.com for "flatten list python" to see people golfing for the shortest/fastest/clearest solutions.

C Smith 12 years, 2 months ago

a simple non-recursive version that modifies in-place. There is a very simple and quick flattener that can be found in the basictypes folder in the latebind.py script by Mike C. Fletcher. The source can be downloaded from

http://sourceforge.net/project/showfiles.php?group_id=87034&package_id=90541&release_id=288585

Here it is:

``````import sys
def flatten(inlist, type=type, ltype=(list,tuple), maxint= sys.maxint):
"""Flatten out a list."""
try:
# for every possible index
for ind in xrange( maxint):
# while that index currently holds a list
while isinstance( inlist[ind], ltype):
# expand that list into the index (and subsequent indicies)
inlist[ind:ind+1] = list(inlist[ind])
#ind = ind+1
except IndexError:
pass
return inlist
``````

I'm not sure why the "type=type" argument is present since "type" is not used in the function. Also, if you omit the last line a copy will not be returned; the modification will only be done in place.

Jordan Callicoat 10 years, 9 months ago

a further simplification... Fletcher's version is really cool! I have a (slight) improvement to make it even simpler:

``````def flatten(l, ltypes=(list, tuple)):
i = 0
while (i &lt; len(l)):
while (isinstance(l[i], ltypes)):
l[i:i+1] = list(l[i])
i += 1
return l
``````

Since len(l) is evaluated each time through the loop, we can just run to the dynamic size of the list, no need to run to maxint and catch the index error.

Noah Rawlins 10 years, 7 months ago

Too simple?

``````>>> flatten([1, 2, [3, []]])
Traceback (most recent call last):
File "", line 1, in
File "", line 4, in flatten
IndexError: list index out of range

or simply...

>>> flatten([[]])
Traceback (most recent call last):
File "", line 1, in
File "", line 4, in flatten
IndexError: list index out of range

need to do something with the inner while loop so that it doesn't crash when the last element to be flattened is an empty list.

noah
``````
Jordan Callicoat 10 years, 5 months ago

Yup, good point... OK, good point. So here is a fixed version to support empty lists (in any position):

``````def flatten(l, ltypes=(list, tuple)):
i = 0
while i OK, good point. So here is a fixed version to support empty lists (in any position):

<pre>
def flatten(l, ltypes=(list, tuple)):
i = 0
while i
``````

</pre>

Jordan Callicoat 10 years, 5 months ago

err, it messed up my post...

``````def flatten(l, ltypes=(list, tuple)):
i = 0
while i &lt; len(l):
if not l[i]:
l.pop(i)
continue
while isinstance(l[i], ltypes):
l[i:i+1] = list(l[i])
i += 1
return l
``````
Greg Anderson 10 years, 3 months ago

Still problems with empty lists. >>> flatten([[[]]])

Traceback (most recent call last):

File "", line 1, in

File "/tmp/python-2596k4V", line 7, in flatten

IndexError: list index out of range

Jordan Callicoat 10 years, 1 month ago

Another fix... OK, this should fix it.

``````def flatten(l, ltypes=(list, tuple)):
i = 0
while i &lt; len(l):
while isinstance(l[i], ltypes):
if not l[i]:
l.pop(i)
if not len(l):
break
else:
l[i:i+1] = list(l[i])
i += 1
return l
``````
Damon McCormick 9 years ago

the last line doesn't copy. It just returns a reference to the in-place-modified input.

Jordan Callicoat 8 years, 6 months ago

Yet another fix... OK, this should cover all the test cases now (thx John Y.).

``````def flatten(l, ltypes=(list, tuple)):
ltype = type(l)
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]
i += 1
return ltype(l)
``````
ukpyr666 7 years, 9 months ago

recursive : [code]def flatten( listIn=[], listOut = [] ): ''' returns flattened listIn ''' for element in listIn: if getattr(element, '__iter__', False): listOut += flatten( element, [] ) else: listOut.append( element) return listOut [/code]

ukpyr666 7 years, 9 months ago

sorry for formatting:

``````def flatten( listIn=[], listOut = [] ):
''' returns flattened listIn '''
for element in listIn:
if getattr(element, '__iter__', False): listOut += flatten( element, [] )
else: listOut.append( element)
return listOut
``````
Giannis Fysakis 7 years ago

<pre> def flattenlist(L): import types Types =dir(types)[:-5] Types.pop(Types.index('StringType')) Types.pop(Types.index('UnicodeType')) Types.pop(Types.index('StringTypes')) Types.pop(Types.index('ListType')) Types.pop(Types.index('ObjectType')) Types.pop(Types.index('TupleType'))

``````        Types = tuple(( eval("types.%s "% i ) for i in  Types))
tmp = []
def core(L):
for i in L:
if isinstance(i,Types):
tmp.append(i)
continue
if type(i) == type(str()):
tmp.append(i)
else:
core(i)
return tmp
return core(L)
``````

<pre>

Giannis Fysakis 7 years ago
``````def flattenlist(L):
Types =dir(types)[:-5]
Types.pop(Types.index('StringType'))
Types.pop(Types.index('UnicodeType'))
Types.pop(Types.index('StringTypes'))
Types.pop(Types.index('ListType'))
Types.pop(Types.index('ObjectType'))
Types.pop(Types.index('TupleType'))
Types = tuple(( eval("types.%s "% i ) for i in  Types))
tmp = []
def core(L):
for i in L:
if isinstance(i,Types):
tmp.append(i)
continue
if type(i) == type(str()):
tmp.append(i)
else:
core(i)
return tmp
return core(L)
``````

sorry for previous post that was a mistake

#### Examples

``````>>> x=[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[['x']]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
>>> flattenlist(x)
['x']
>>> x=[[[[[[[[[[[[[2,3,4,{'a':[]}]]]]]]]]]]]],flattenlist]
>>> flattenlist(x)
[2, 3, 4, {'a': []}, <function flattenlist at 0x1a05320>]
``````