Python recursion: nested list from flat list

Question

I need figuring out how to create (what I think needs to be) a recursive function. My brain has never coped well with recursion.

I have a flat collection of items, that needs to be turned into a nested collection based on a value in each item. Each item has, among other attributes, a type. One possible item.type is "group header". Each "group header" will be closed by a "group footer". I need to nest the collection based on those two types.

The collection might look like this:

item 1: type = blurb
item 2: type = group header
item 3: type = question
item 4: type = question
item 5: type = group header
item 6: type = question
item 7: type = question
item 8: type = group footer
item 9: type = question
item 10: type = group footer

I want to make that collection look more like this:

item 1: blurb
item 2: header, item 10: footer
- item 3: question
- item 4: question
- item 5: group header, item 8: footer
- - item 6: question
- - item 7: question
- item 9: question

There can be any depth of nesting, hence (I think) the need for recursion.

Any pointers on how to do it greatly appreciated. I simply cannot get my head around it, and I can't find an example online where a tag (in my case, "group footer") is used to jump back up a nest level.

Here are the beginnings of a python fiddle to work with: http://pythonfiddle.com/recursion-fiddle-ninety-nine

Example data from link:

test_data = [{"id":1, "type":"blurb", "info":"This is the blurb"},
            {"id":2, "type":"header", "info":"This is the first group header"},
            {"id":3, "type":"question", "info":"This is the first question"},
            {"id":4, "type":"question", "info":"This is the second question"},
            {"id":5, "type":"header", "info":"This is the second group header"},
            {"id":6, "type":"question", "info":"This is the third question"},
            {"id":7, "type":"question", "info":"This is the fourth question"},
            {"id":8, "type":"footer", "info":"This is the footer for the second header"},
            {"id":9, "type":"question", "info":"This is the fifth question"},
            {"id":10, "type":"footer", "info":"This is the footer for the first header"}]

thanks in advance

Jay

@PrakashKuma that is not necessary if you just write a recursive function. — chtenb
– chtenb, Commented Jan 1, 2015 at 11:49
@Chiel92 Yes, that's true but what he wrote is this :My brain has never coped well with recursion: , so i thought that stack will be a better option for him. Also performance wise using stack will be better than recursion. — Prakash Kuma
– Prakash Kuma, Commented Jan 1, 2015 at 11:52
Please show (in your question) the original flat list "collection". — martineau
– martineau, Commented Jan 1, 2015 at 16:13

Aran-Fey · Accepted Answer · 2015-01-01 11:50:52Z

4

I don't know how exactly you want the resulting list to be formatted, but here you go:

nested_data = []
stack= []
for item in test_data:
    if item['type']=='header': # if it's a header
        # add [item] to the list (the footer will be appended to this later)
        header= [[item]]
        nested_data.append(header)
        # push this list onto the stack so we can continue appending to it
        # after we've found the footer
        stack.append(nested_data)
        nested_data= header
    elif item['type']=='footer':
        # if it's a footer, pop the last list off the stack
        nested_data= stack.pop(-1)
        # and append the footer after the header so that
        # [header, footer] is the first item
        nested_data[-1][0].append(item)
    else:
        # if it's just a boring ol' item, all we need do is append it
        nested_data.append(item)

This produces (the nested_data variable holds the result):

[
  {
    "info": "This is the blurb", 
    "type": "blurb", 
    "id": 1
  }, 
  [
    [
      {
        "info": "This is the first group header", 
        "type": "header", 
        "id": 2
      }, 
      {
        "info": "This is the footer for the first header", 
        "type": "footer", 
        "id": 10
      }
    ], 
    {
      "info": "This is the first question", 
      "type": "question", 
      "id": 3
    }, 
    {
      "info": "This is the second question", 
      "type": "question", 
      "id": 4
    }, 
    [
      [
        {
          "info": "This is the second group header", 
          "type": "header", 
          "id": 5
        }, 
        {
          "info": "This is the footer for the second header", 
          "type": "footer", 
          "id": 8
        }
      ], 
      {
        "info": "This is the third question", 
        "type": "question", 
        "id": 6
      }, 
      {
        "info": "This is the fourth question", 
        "type": "question", 
        "id": 7
      }
    ], 
    {
      "info": "This is the fifth question", 
      "type": "question", 
      "id": 9
    }
  ]
]

answered Jan 1, 2015 at 11:50

Aran-Fey

44k13 gold badges113 silver badges161 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

John Over a year ago

That's a great help, thanks! Unfortunately it's nesting the headers and footers at the same depth as the questions inside them. Would it be too much to ask you to tweak it so the headers are up a level higher than the questions they contain? I'm trying to figure out how you do that, but I don't yet understand what you've done well enough to adjust it.

Aran-Fey Over a year ago

Just to make sure I understand correctly, you want it to be like [[header, footer], [item1, item2, ...]]?

Collectives™ on Stack Overflow

Python recursion: nested list from flat list

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related