ActiveState Code

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.

Comments

1. 1. At 7:50 a.m. on 19 jan 2005, Anonymous said:

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

2. 2. At 2:27 a.m. on 11 apr 2005, C Smith said:

   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.

3. 3. At 4:17 p.m. on 5 sep 2006, Jordan Callicoat said:

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

4. 4. At 5:34 p.m. on 21 nov 2006, Noah Rawlins said:

   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
   

5. 5. At 8:24 p.m. on 25 jan 2007, Jordan Callicoat said:

   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>

6. 6. At 8:25 p.m. on 25 jan 2007, Jordan Callicoat said:

   err, it messed up my post...

   def flatten(l, ltypes=(list, tuple)):
     i = 0
     while i < 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
   

7. 7. At 9:35 a.m. on 21 mar 2007, Greg Anderson said:

   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

8. 8. At 10:49 p.m. on 14 may 2007, Jordan Callicoat said:

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

   def flatten(l, ltypes=(list, tuple)):
     i = 0
     while i < 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
   

9. 9. At 12:03 a.m. on 29 jun 2008, Damon McCormick said:

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

10. 10. At 12:22 a.m. on 13 dec 2008, Jordan Callicoat said:

    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)
    

11. 11. At 1:50 a.m. on 10 sep 2009, ukpyr666 said:

    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]

12. 12. At 1:54 a.m. on 10 sep 2009, ukpyr666 said:

    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
    

Sign in to comment

Tags

none