Nesting lists in python

Question

I'm trying to solve a problem that, unfortunately, goes beyond my capacity. I have a series of nested lists and while iterating over them, in case the next element is a list I want to append it as an attribute of my current element. As usual, an example is better than my poor English (here's some code to copy and paste):

class T(object):
    def __init__(self, id, children):
         self.id = id 
         self.children = children or []

    def __repr__(self):
         return u"T(id={0}, children={1})".format(self.id, self.children) 


# first a short example
l0 = [T(id=1, children=[]), T(id=2, children=[]), [T(id=3, children=[]), 
      T(id=4, children=[]), [T(id=5, children=[])]]]

As you can see l0 has 3 elements and the last one is list of three elements: what I need is to append the last list to the previous element that is not a list (and recursively) Expected output:

l1 = magic(l0)    
[T(id=1, children=[]), T(id=2, children=[T(id=3, children=[]), T(id=4, children=[T(id=5, children=[])])])]

Hope somebody can share some advice to solve this, I've already invested a lot of hours and I'm not even close to solve it.

EDIT

For completeness, here's a little more complex example

l0 = [T(children=[], id=1),
      T(children=[], id=2),
      T(children=[], id=3),
      [T(children=[], id=40),
       T(children=[], id=41),
       T(children=[], id=42),
       T(children=[], id=43),
       T(children=[], id=44),
       T(children=[], id=45),
       [T(children=[], id=50),
        T(children=[], id=51),
        T(children=[], id=52),
        T(children=[], id=54),
        [T(children=[], id=60),
         T(children=[], id=61),
         T(children=[], id=62),
         T(children=[], id=63),
         [T(children=[], id=70)],
         T(children=[], id=64)]]],
      T(children=[], id=8),
      T(children=[], id=9)]

I built a doctest using @rik-poggi function as example and so far it seems to be ok:

>>> from magic_bag import magic
>>> class T(object):                                                        
...     def __init__(self, id, children):                                   
...         self.id = id                                                    
...         self.children = children or []                                  
...                                                                         
...     def __repr__(self):                                                 
...         return u"T(children={0}, id={1})".format(self.children, self.id)
...                                                                         
>>> l0 = [T(id=1, children=[]), T(id=2, children=[]), T(id=3, children=[]), 
... [T(id=40, children=[]), T(id=41, children=[]), T(id=42, children=[]),   
... T(id=43, children=[]), T(id=44, children=[]), T(id=45, children=[]),    
... [T(id=50, children=[]), T(id=51, children=[]), T(id=52, children=[]),   
... T(id=54, children=[]), [T(id=60, children=[]), T(id=61, children=[]),   
... T(id=62, children=[]), T(id=63, children=[])]]], T(id=8, children=[]),  
... T(id=9, children=[])]                                                   
>>> l1 = magic(l0)                                              
>>> l1[0]                                                                   
T(children=[], id=1)                                                        
>>> l1[1]                                                                   
T(children=[], id=2)                                                        
>>> l1[3]                                                                   
T(children=[], id=8)                                                        
>>> l1[4]                                                                   
T(children=[], id=9)                                                        
>>> l1[5]                                                                   
Traceback (most recent call last):                                          
    ...                                                                     
IndexError: list index out of range                                         
>>> l1[2].children[5].children[3]                                           
T(children=[T(children=[], id=60), T(children=[], id=61), T(children=[], id=62), T(children=[], id=63)], id=54)
>>> l0 = [T(id=1, children=[]), T(id=2, children=[]), T(id=3, children=[]), 
... [T(id=40, children=[]), T(id=41, children=[]), T(id=42, children=[]),   
... T(id=43, children=[]), T(id=44, children=[]), T(id=45, children=[]),    
... [T(id=50, children=[]), T(id=51, children=[]), T(id=52, children=[]),   
... T(id=54, children=[]), [T(id=60, children=[]), T(id=61, children=[]),   
... T(id=62, children=[]), T(id=63, children=[]), [T(id=70, children=[])],  
... T(id=64, children=[])]]], T(id=8, children=[]), T(id=9, children=[])]   
>>> l1 = magic(l0)                                              
>>> l1[2].children[5].children[0].id                                        
50                                                                          
>>> len(l1[2].children[5].children[3].children)                             
5                                                                           
>>> l1[2].children[5].children[3].children[3].children                      
[T(children=[], id=70)]                                                     
>>> l1[2].children[5].children[3].children[4].id==64                        
True

Using @rob-wouters alternative, it passes the same test too so for the test cases I tried both work ok. I will keep Rik's because I think a standalone function can be more handy for the cases when I need this kind of behavior.

Question aside, if the was a prize for "worst variable name of the month", I'd nominate "l0" . It is nearly unreadable, as it resembles both the number "10" and the interjection "lo" and the word "io" all at the same time. — jsbueno
– jsbueno, Commented Jan 17, 2012 at 1:49
Yeah, sorry about that, I throw my last neurons asking the question! :) — MayVimmer Imeil
– MayVimmer Imeil, Commented Jan 17, 2012 at 2:18
@agarrett actually no. I should have added a more complete example. — MayVimmer Imeil
– MayVimmer Imeil, Commented Jan 17, 2012 at 2:19
@MayVimmerImeil I started working on your problem and found several corner cases, it isn't clear what to do in each case. For example (and simplifying a lot the notation, but you get the idea): [[1] [2]] or [[1] 2] or [1 [2] [3]] or [1 [2] [3] 4] or [1 [2 [3]]] — Óscar López
– Óscar López, Commented Jan 17, 2012 at 2:32

Rob Wouters · Accepted Answer · 2012-01-17 15:56:56Z

3

This is how I would do it:

class T(object):
    def __init__(self, id, children):
         self.id = id 
         self.children = children or []

    def add_children(self, children):
        for child in children:
            if isinstance(child, list):
                self.children[-1].add_children(child)
            else:
                self.children.append(child)

    def __repr__(self):
         return u"T(id={0}, children={1})".format(self.id, self.children) 


l0 = [T(id=1, children=[]),
      T(id=2, children=[]), [T(id=3, children=[]), T(id=4, children=[]),
                            [T(id=5, children=[])]]]

root = T(id=0, children=[])
root.add_children(l0)
print(root.children)

If you really want a standalone method, instead of having two functions that handle the same case you can use the following:

def add_children(node, children):
    for child in children:
        if hasattr(child, '__iter__'):
            add_children(node.children[-1], child)
        else:
            node.children.append(child)

def create_tree(lst):
    root = T(id=0, children=[])
    add_children(root, lst)
    return root.children

print(create_tree(l0))

This is a bit more elegant since it avoids a lot of repetitive code compared to having two functions that are nearly the same. I did alter my isinstance check in favor of checking for __iter__ which allows more flexibility in how you store your list of children.

edited Jan 17, 2012 at 15:56

answered Jan 17, 2012 at 1:37

Rob Wouters

16.4k3 gold badges44 silver badges36 bronze badges

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

2 Comments

MayVimmer Imeil Over a year ago

Thanks Rob, I will test it and let you guys know how it went

Rob Wouters Over a year ago

@MayVimmerImeil, after reading your edited answer I've suggested a standalone method which I think is a bit more concise and readable. Let me know what you think.

Rik Poggi · Accepted Answer · 2012-01-17 02:03:07Z

1

I came up with this:

def append_children(parent, iterable):
    last = None
    for i in iterable:
        if hasattr(i, '__iter__'):
            append_children(last, i)
        else:
            parent.children.append(i)
            last = i

def magic(lst):
    result = []
    for i in lst:
        if hasattr(i, '__iter__'):
            append_children(result[-1], i)
        else:
            result.append(i)
    return result

Example:

>>> l_in = [T(id=1, children=[]), T(id=2, children=[]), [T(id=3, children=[]), 
...         T(id=4, children=[]), [T(id=5, children=[])]]]
>>> l_expected = [T(id=1, children=[]),
...               T(id=2, children=[T(id=3, children=[]), 
...                                 T(id=4, children=[T(id=5, children=[])])])]
>>> l_ouput = magic(l_in)
>>> repr(l_output) == repr(l_expected)
True

edited Jan 17, 2012 at 2:03

answered Jan 17, 2012 at 1:16

Rik Poggi

29.5k7 gold badges69 silver badges84 bronze badges

3 Comments

David Alber Over a year ago

In this situation, you can delete your answer, edit it while deleted, and undelete it once you feel satisfied with your answer.

MayVimmer Imeil Over a year ago

Thanks Rik, I will test it and let you know how it went

Rik Poggi Over a year ago

@MayVimmerImeil: it seems that you may have a lot of sub/special cases, so I'm a little curious to know if this code can handle them.

Collectives™ on Stack Overflow

Nesting lists in python

2 Answers 2

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related