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

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). [Edit]: 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!

14 comments

jackdied 19 years, 2 months ago  # | flag

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 18 years, 11 months ago  # | flag

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 17 years, 6 months ago  # | flag

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 17 years, 4 months ago  # | flag

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 17 years, 2 months ago  # | flag

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 17 years, 2 months ago  # | flag

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 17 years ago  # | flag

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 16 years, 10 months ago  # | flag

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 15 years, 9 months ago  # | flag

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

Jordan Callicoat 15 years, 3 months ago  # | flag

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 14 years, 6 months ago  # | flag

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 14 years, 6 months ago  # | flag

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 13 years, 10 months ago  # | flag

<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 13 years, 10 months ago  # | flag
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>]
Created by Orri Ganel on Thu, 13 Jan 2005 (PSF)
Python recipes (4591)
Orri Ganel's recipes (2)

Required Modules

Other Information and Tasks