Python-Ref > Recursion > Flattening lists of lists
 
 

<-^^->
Moduly
Knihovní funkce

Flattening lists of lists

Recusion is commonly used to process structures that contain other similar structures in itself.
In this case a sum of numbers contained in a complex structure built from lists is computed.
Expand/Shrink
Zdroj: (recursion2-1.py)
  1   l = [[1,2,3],
  2        [4,5,6],
  3        [7,8,9,[10,11,12],13],
  4        [[1],[2],[3]],
  5        [1,3,5,[7],[],[5,6]]]
  6   
  7   
  8   def deep_sum( xs):
  9       s = 0
 10       for x in xs:
 11           if type( x) == type( []):
 12               s += deep_sum( x)  # the recursion continues for lists
 13           else:
 14               s += x             # but stops for simple values
 15       return s
 16   
 17   print deep_sum( l)
stdout:
124
Doba běhu: 13.9 ms
The same function run on a simpler data structure demonstrates the order in which steps are evaluated. We could call such an algorithm depth-first, because it completely evaluates one item before going to try another.
Expand/Shrink
Zdroj: (recursion2-2.py)
  1   l = [[1,2,3],
  2        [4,5,6],
  3        [[1],[2],[3]],
  4        [[],[5,6]]]
  5   
  6   
  7   def deep_sum( xs):
  8       s = 0
  9       for x in xs:
 10           print x
 11           if type( x) == type( []):
 12               s += deep_sum( x)  # the recursion continues for lists
 13           else:
 14               s += x             # but stops for simple values
 15       return s
 16   
 17   deep_sum( l)
stdout:
[1, 2, 3]
1
2
3
[4, 5, 6]
4
5
6
[[1], [2], [3]]
[1]
1
[2]
2
[3]
3
[[], [5, 6]]
[]
[5, 6]
5
6
Doba běhu: 14.2 ms
A small adjustment of the algorithm can be used to convert the complex list structure to a flat list.
Expand/Shrink
Zdroj: (recursion2-3.py)
  1   l = [[1,2,3],
  2        [4,5,6],
  3        [7,8,9,[10,11,12],13],
  4        [[1],[2],[3]],
  5        [1,3,5,[7],[],[5,6]]]
  6   
  7   
  8   def flatten( xs):
  9       s = []
 10       for x in xs:
 11           if type( x) == type( []):
 12               s += flatten( x)  # + is used for list concatenation, we could also use s.extend( flatten( x))
 13           else:
 14               s += [x]          # we could also use s.append( x)
 15       return s
 16   
 17   print flatten( l)
 18   print sum( flatten( l))  # the sum should be the same as for the first example
stdout:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 3, 1, 3, 5, 7, 5, 6]
124
Doba běhu: 13.9 ms