Nested list to string

Question

I have a list of instances of class Test. This class have method like name and parent

[Test('a', ''), Test('b', ''), Test('c', 'a'), Test('d', 'a'), Test('e', 'c')]

First argument is name, second parent. Parent arg is simply a arg name of parent class. I want convert this list to string like:

Test('a', '')
  |-- Test('c', 'a')
        |-- Test('e', 'c')
  |-- Test('d', 'a')
Test('b', '')

I looking for the most CPU-effective way to convert this list to string. Items in list can be nested at multiples (10,100, 1000, ..) levels, and I don't care about memory used.

Do you have a specific question or spot where you are stuck? Can you post the code you've tried so far and are getting an error with, or are you looking for thoughts on best solution? — Steven Mastandrea
– Steven Mastandrea, Commented Jul 3, 2011 at 4:27
Edited. Sorry for this :) I looking for code or any idea to make this in CPU-effective way. — Galmi
– Galmi, Commented Jul 3, 2011 at 4:39

Petar Ivanov · Accepted Answer · 2011-07-03 05:00:11Z

2

Here is code that works as is. Basically convert the array into a tree and then use recursive DFS to print it (you can use iterative DFS if you want):

class Test:
    def __init__(self, name, parent):
        self.name = name
        self.parent = parent
    def __repr__(self):
        return "Test('"+self.name+"', '"+self.parent+"')"



li = [Test('a', ''), Test('b', ''), Test('c', 'a'), Test('d', 'a'), Test('e', 'c')]

dict = {"":(None,[])} #name to (node,children)
#add nodes
for item in li:
    dict[item.name] = (item, [])
#add children
for item in li:
    dict[item.parent][1].append(dict[item.name])

def printTree(dict, name, indent):
    newIndent=indent
    if name!="":
        print(indent + str(dict[name][0]))
        if indent == "": newIndent="  |-- "
        else: newIndent = "      "+indent
    for child in dict[name][1]:
        printTree(dict, child[0].name, newIndent) 


printTree(dict, "", "")

answered Jul 3, 2011 at 5:00

Petar Ivanov

93.4k11 gold badges84 silver badges95 bronze badges

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

5 Comments

user780363 Over a year ago

you create N references to each item (where N is the deepness). That code will be bad for large inputs...

user780363 Over a year ago

you have: {'': [a: [c: e, d], b], a: [c: e, d], b, c: e, d, e}

Petar Ivanov Over a year ago

you do realize that dict["a"][1][0] is dict["c"] is True in my code, right? There is exactly one object per name, just multiple references.

Petar Ivanov Over a year ago

so there are only at most two references to each node - one in the dict and one from the parent

user780363 Over a year ago

That's exactly what I wrote: "you create N references to each item"... still bad IMHO

JBernardo · Accepted Answer · 2011-07-03 04:47:48Z

0

You should use another container, like that:

class Test:
    def __init__(self, name, sub=None):
        self.name = name
        self.sub = sub if sub is not None else []

elements = [Test('a', [Test('c', [Test('e')]), Test('d')]), Test('b')]

then just iterate elements to print:

def show(x, indent=0):
    for i in x:
        print('\t'*indent + 'Test(%r)' % i.name)
        show(i.sub, indent+1)

show(elements)

should print:

Test('a')
    Test('c')
        Test('e')
    Test('d')
Test('b')

You may change the indentation to anything you prefer (I'm using tabs).

answered Jul 3, 2011 at 4:47

JBernardo

33.6k13 gold badges92 silver badges120 bronze badges

Comments

Rusty Rob · Accepted Answer · 2011-07-03 05:15:48Z

0

If you end up using DFS as fiver suggested you could use networkx

import networkx as nx
stuff=[('a', ''), ('b', ''), ('c', 'a'), ('d', 'a'), ('e', 'c')]
G=nx.DiGraph()
for i in stuff:
    G.add_edge(i[1],i[0])
print G.adj

Then it is a mater of iterating it with DFS

answered Jul 3, 2011 at 5:15

Rusty Rob

17.3k10 gold badges103 silver badges121 bronze badges

Collectives™ on Stack Overflow

Nested list to string

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related