Flatten nested list or generate blocks of nested lists
Flatten nested lists into linear set of elements using list comprehension and recursive methods. Chop a flat list into sublists of equal size. Create an infinite list using circular referencing.
Page contents
- Flatten nested list by one level
- Drawbacks of fixed level flattening
- Recursively flatten a nested list
- Working with nested data structures
- Creating simple nested lists
- Chop flat list into nested blocks
- Nested circular referencing
- Summary of methods
Flatten nested list by one level
A list of homogeneously nested elements can be simplified into a flat list structure elegantly using a list comprehension.
Py3: Flatten single level nested list using comprehension
# nested list of tuples
nested = [(1,2),(3,4),(5,6,7),('a','bc','d')]
# list comprehension for single level nesting
flat = [t for item in nested for t in item]
print(flat)
# required flattened list of elements
#= [1,2,3,4,5,6,7,'a','bc','d']
While list comprehension is a compact way to perform flattening, the same result can be attained with conventional for loops.
Py3: Flatten with conventional for loops
# list of mixed tuples to flatten
nested = [(1,2),(3,4),(5,6,7),('a','bc','d')]
flat = []
# loop over tuples in list
for item in nested:
# loop over elements within each tuple
for t in item:
flat.append(t)
print(flat)
# flattened list
#= [1,2,3,4,5,6,7,'a','bc','d']
Notes: Homogeneous flattening
Homogeneous nesting is the case where elements and sub-elements are embedded in a similar way to similar sub-levels. If the structure is homogeneous, then loops or list comprehension can be used to simplify and flatten them out. This is also the quickest method to get the required result. If the nesting is irregular, where elements are embedded at different levels, then more logical steps are needed to discriminate these sub-elements and flatten them appropriately.
Drawbacks of fixed level flattening
Flattening with fixed loop structure is adequate for homogeneously nested lists. There are limitations to simple nested loops for flattening for lists that are irregularly nested. This can cause incomplete flattening or errors.
Py3: Incomplete flattening of deep pockets
# pockets of deeper nesting
# ('a',3) is double nested
nested = [(1,2,('a',3)),('b',4)]
# flatten with comprehension
semiflat = [t for item in nested for t in item]
print(semiflat)
# deeper nested elements are not flattened
#= [1,2,('a',3),'b',4]
Extra nested items are not properly flattened with simple flatten methods. On the other hand loops will causing errors if expected nested sub-elements are not available.
Py3: Less nested sub-elements
# mixed elements, flat and nested
nested = [('a',1),'b',2]
# flatten with comprehension
nonflat = [t for item in nested for t in item]
# loop expected element 2 to be an iterable
# so inner loop fails
# nonflat = ['a', 1, b #error#...
#= TypeError: 'int' object is not iterable
Notes: Non-homogeneous sub-elements
Examples demonstrate that deep pockets of nesting are not completely flattened. The desired outcome can be to flatten by a single level. For those cases the nested comprehension would still work best.
However when it is unclear apriori what the level of nesting will be for the list to be flattened, then each element needs to be evaluated for further flattening. A blind single level flattening will not work. When sub-element is iterable and can be flattened, then a recursive logic should keep flattening children. When the basic element is not a candidate for flattening, then it should be added to the flat output list without further flattening to avoid errors.
Recursively flatten a nested list
Complete flattening of an irregular nested list needs a recursive algorithm to detect if each element and sub-element is a candidate for further flattening.
Py3: Recursive flatten algorithm for list
# recursive function to flatten a nested list completely
#-------------------------------------------------------
def flatall(nested_object):
# gather stores the final flattened list
gather = []
for item in nested_object:
# will flatten lists, tuples and sets
# will not operate on string, dictionary
if isinstance(item, (list, tuple, set)):
gather.extend(flatall(item))
else:
gather.append(item)
return gather
#-------------------------------------------------------
# irregular nested list
nested = [[1,[2,{3,4}]],(5,'abc',{6,('d',7)},[8,9]),'e',10]
# call function flatall
flatlist = flatall(nested)
print(flatlist)
# fastest conversion from nested to flat list
# does not convert strings into letters
#= [1,2,3,4,5,'abc',6,'d',7,8,9,'e',10]
Generator form of flattening to save memory and be more responsive.
Py3: Recursive generator to flatten nested list
# recursive single element generator
#-------------------------------------------------------
def flatgen(nested_object):
for item in nested_object:
# will flatten lists, tuples and sets
# will not operate on string, dictionary
if isinstance(item, (list, tuple, set)):
yield from flatgen(item)
else:
yield item
#-------------------------------------------------------
# irregular nested list
nested = [[1,[2,{3,4}]],(5,'abc',{6,('d',7)},[8,9]),'e',10]
# declare a generator
fgen = flatgen( nested )
# get first 6 elements
for count, item in enumerate(fgen, 1):
if count > 6:
break
print(item)
#= 1
# 2
# 3
# 4
# 5
# abc
# convert all generator elements into a list
flatlist = list(fgen)
print(flatlist)
#= [1,2,3,4,5,'abc',6,'d',7,8,9,'e',10]
Notes: Iterative or recursive flattening
Iterative flattening achieves fully flattened lists. It discriminates between iterable elements belonging to lists, sets, tuples from other data types. Only target iterable data elements are recursively flattened.
Maintaining a flat list to which elements are added duplicates memory assignment, and can be expensive for very large lists. A generator version executes slightly slower when whole list is evaulated , but is very memory efficient and responsive. Consider the case when each element has to be processed further. A generator version will return a single element each time on request. There is very little delay in getting one element for more processing. It is not required to wait for the whole data to be flattened. So realtime memory efficient version would be a generator.
Iterables like strings are not to be segmented into letters. This is a choice for this implementation. Other implementations may break up strings into individual letters. Dictionaries can have nested objects too, and they can be flattened with added logic. We need to consider what to do with the keys and values. The elements can be aggregated as key, value pairs or ordered into sequences. So more decisions are needed to operate on strings and dictionaries, and they can be easily augmented.
Working with nested data structures
Real life arrangement of data requires nesting. Many-to-one links is a good example where multiple sub-elements belong to a single main element. The number of sub-elements can vary, and can be explicitly declared.
Py3: Hierarchical many to one data structures
# nested list data structure for:
# continent, % landmass, top 10 populous cities world
world = [
['Africa',20.4,['Cairo']],
['Antarctica',9.2,[]],
['Asia',29.5, ['Tokyo','Delhi','Shanghai','Mumbai','Beijing','Osaka']],
['Australia',5.9,[]],
['Europe',6.8,[]],
['North America',16.5,['New York','Mexico City']],
['South America',12.0,['Sao Paulo']]
]
# gather all nested city names
top10 = []
for cont, area, cities in world:
top10.extend(cities)
print(top10)
#= ['Cairo','Tokyo','Delhi','Shanghai','Mumbai','Beijing',
# 'Osaka','New York','Mexico City','Sao Paulo']
Creating simple nested lists
To nest a list within another list to create a hierarchical structure, just use the append command.
Py3: Append list into another list
# simple list
a = [1,2,3]
# short hand nesting to create nested list
b = [a]
print(b)
#= [[1,2,3]]
# alternate version using append
b = []
b.append(a)
print(b)
#= [[1,2,3]]
Notes: Nesting with append
Append creates an element within a list. Appending a list, creates a nested list embedded one level down. Repeated appending can increase the depth of nesting.
Chop flat list into nested blocks
Starting from a flat nested list, we can chop it up into segments and create nested blocks. Chopping a flat list into equal nested blocks of elements essentially converts one dimensional list to a two dimensional list.
Py3: Chop flat list to two dimensions
# function to chop a flat list into rows
# of fixed column size ncols
# flist is the flat list provided
#-------------------------------------------------------
def choplist(flist, ncols):
itr = iter(flist)
return [[*grp] for grp in zip(*[itr]*ncols)]
#-------------------------------------------------------
# start with flat list
pylist = [*range(12)]
#= [0,1,2,3,4,5,6,7,8,9,10,11]
# Ex1: convert to 4 column nested list
c4 = choplist(pylist, 4)
print(c4)
#= [ [0, 1, 2, 3],
# [4, 5, 6, 7],
# [8, 9, 10, 11]
# ]
# all 12 elements are arranged
# Ex2: convert to 5 column nested list
c5 = choplist(pylist, 5)
print(c5)
#= [ [0, 1, 2, 3, 4],
# [5, 6, 7, 8, 9]
# ]
# only 10 elements are used
# extra elements are ignored
Notes: List of lists
Lists of lists or nested lists are very common data structures. Simple nesting can be achieved by appending existing lists. This is done to group similar types or related data. Flat lists can be nested by providing rows or column counts and a method to chop up the linear list into nested structures. The flat list structure is converted into an iterator and replicated by required column count. The zip function requests elements from each of the iterators. Since all iterators are referenced to the single iterator, it counts elements equal to the number of columns. The elements are grouped into a list and appended to the main list creating a two dimensional structure.
Nested circular referencing
Circular referencing occurs when a list contained within itself. The effects of circular nesting looks like an infinite dimensional nesting, and can be confusing.
Py3: Circular nesting
alist = [0,1,2]
# embed list within itself
alist.append(alist)
print(alist)
#= [0,1,2,[...]]
# print each element in alist
for i in alist:
print(i)
#= 0
# 1
# 2
# [0,1,2,[...]]
# seemingly endless number of elements!
# use flatgen (see previous) to flatten circular list
# show first 5 elements
fgen = flatgen( alist )
for count, item in enumerate(fgen, 1):
if count > 5:
break
print(item)
#= 0
# 1
# 2
# 0
# 1
# seemingly generates cyclic set of elements
# change an element
alist[0] = 5
for i in alist:
print(i)
#= 5
# 1
# 2
# [5,1,2,[...]]
# more items than the first element have changed
Notes: Circular nesting artifact of referencing
Python stores data by referencing. When a list is created it has a reference identification which is an integer record number id(object). If this reference id is added to the list elements by assigning the list to itself, then we get a circular reference. What we have here is a list, and the reference to itself. The data is finite. Changing elements of the list naturally changes the base data. The references to itself point to the same location and display the changes. Such a circular list can have some interesting applications, but extreme care is needed here.
Summary of methods
Recap of functions and methods to modify nesting.
| Method/Statement | Property |
|---|---|
| list comprehension | flattens simple homogeneous nesting |
| flatall() | flattens iteratively, fast but memory intensive |
| flatgen() | flattens iteratively, generator version, efficient and responsive |
| choplist() | block nesting of one to two dimensions |
