Expand and flatten a ragged nested list

Question

I know that the topic of smoothing a nested list has been discussed in detail before, but I think that my task is a little different, and I could not find any information.

I am writing a scraper, and as an output I get a nested list. Top-level list items must be rows for data in the form of spreadsheets. However, since nested lists often have different lengths, I need to expand them before aligning the list.

Here is an example. I have

[ [ "id1", [["x", "y", "z"], [1, 2]], ["a", "b", "c"]], [ "id2", [["x", "y", "z"], [1, 2, 3]], ["a", "b"]], [ "id3", [["x", "y"], [1, 2, 3]], ["a", "b", "c", ""]] ] 

The conclusion that I ultimately want is

  [[ "id1", "x", "y", z, 1, 2, "", "a", "b", "c", ""], [ "id2", "x", "y", z, 1, 2, 3, "a", "b", "", ""], [ "id3", "x", "y", "", 1, 2, 3, "a", "b", "c", ""]] 

However an interim list like this

  [ [ "id1", [["x", "y", "z"], [1, 2, ""]], ["a", "b", "c", ""]], [ "id2", [["x", "y", "z"], [1, 2, 3]], ["a", "b", "", ""]], [ "id3", [["x", "y", ""], [1, 2, 3]], ["a", "b", "c", ""]] ] 

which I can then just smooth out, will also be fine.

Top-level list items (rows) are created at each iteration and added to the complete list. I think in the end it’s easier to convert a complete list?

The structure in which the elements are nested must be the same, however I cannot be sure of that. I think I have a problem if the structure is where it looks.

  [ [ "id1", [[x, y, z], [1, 2]], ["a", "b", "c"]], [ "id2", [[x, y, z], [1, 2, 3]], ["bla"], ["a", "b"]], [ "id3", [[x, y], [1, 2, 3]], ["a", "b", "c", ""]] ] 

which should become

  [[ "id1", x, y, z, 1, 2, "", "", "a", "b", "c", ""], [ "id2", x, y, z, 1, 2, 3, "bla", "a", "b", "", ""], [ "id3", x, y, "", 1, 2, 3, "", "a", "b", "c", ""]] 

Thanks for any comments, and please excuse me if this is trivial, I'm pretty new to Python.

Answer 1

I have a simple solution for the case of "the same structure" using the recursive generator and the izip_longest function from itertools . This code is for Python 2, but with a few tweaks (noted in the comments) you can get Python 3 to work:

 from itertools import izip_longest # in py3, this is renamed zip_longest def flatten(nested_list): return zip(*_flattengen(nested_list)) # in py3, wrap this in list() def _flattengen(iterable): for element in izip_longest(*iterable, fillvalue=""): if isinstance(element[0], list): for e in _flattengen(element): yield e else: yield element 

In Python 3.3, this will become even simpler thanks to PEP 380 , which will allow the recursive step for e in _flatengen(element): yield e to become yield from _flattengen(element) .

Answer 2

In fact, there is no solution for the general case when the structure is not the same. For example, a normal algorithm would match ["bla"] with ["a", "b", "c"] , and the result would be

  [ [ "id1", x, y, z, 1, 2, "", "a", "b", "c", "", "", ""], [ "id2", x, y, z, 1, 2, 3, "bla", "", "", "", "a", "b"], [ "id3", x, y, "", 1, 2, 3, "a", "b", "c", "", "", ""]] 

But if you know that you will have several lines, each of which will start with the identifier a, and then the nested list structure, the algorithm below should work:

 import itertools def normalize(l): # just hack the first item to have only lists of lists or lists of items for sublist in l: sublist[0] = [sublist[0]] # break the nesting def flatten(l): for item in l: if not isinstance(item, list) or 0 == len([x for x in item if isinstance(x, list)]): yield item else: for subitem in flatten(item): yield subitem l = [list(flatten(i)) for i in l] # extend all lists to greatest length list_lengths = { } for i in range(0, len(l[0])): for item in l: list_lengths[i] = max(len(item[i]), list_lengths.get(i, 0)) for i in range(0, len(l[0])): for item in l: item[i] += [''] * (list_lengths[i] - len(item[i])) # flatten each row return [list(itertools.chain(*sublist)) for sublist in l] l = [ [ "id1", [["x", "y", "z"], [1, 2]], ["a", "b", "c"]], [ "id2", [["x", "y", "z"], [1, 2, 3]], ["a", "b"]], [ "id3", [["x", "y"], [1, 2, 3]], ["a", "b", "c", ""]] ] l = normalize(l) print l 

Answer 3

 def recursive_pad(l, spacer=""): # Make the function never modify it arguments. l = list(l) is_list = lambda x: isinstance(x, list) are_subelements_lists = map(is_list, l) if not any(are_subelements_lists): return l # Would catch [[], [], "42"] if not all(are_subelements_lists) and any(are_subelements_lists): raise Exception("Cannot mix lists and non-lists!") lengths = map(len, l) if max(lengths) == min(lengths): #We're already done return l # Pad it out map(lambda x: list_pad(x, spacer, max(lengths)), l) return l def list_pad(l, spacer, pad_to): for i in range(len(l), pad_to): l.append(spacer) if __name__ == "__main__": print(recursive_pad([[[[["x", "y", "z"], [1, 2]], ["a", "b", "c"]], [[[x, y, z], [1, 2, 3]], ["a", "b"]], [[["x", "y"], [1, 2, 3]], ["a", "b", "c", ""]] ])) 

Edit: Actually, I misunderstood your question. This code solves a slightly different problem.