CODEWITHSUNDEEP
pythonlistrecursiontreegenerator
dvjz
dvjz

Reputation: 408

From list to tree representation

Hello I have a list (in Python 3) like this :

lista=[ ['a','b','c','d'],['b','f','g'],['c','h','i'],['d'],['h'],['i'],['f'],['g']]

and I'm trying to translate it in a nested list like this

['a',['b',['f'],['g']],['c',['h'],['i']],['d']]]

so it's like this tree :

              a
            / | \
          b   c  d
         /\   /\
       f  g   h i

I thought to use a generator like this

listb = [ lista[0][0]] + [x for x in lista[1:] ]

but I don't know how to iterate recursively through the whole list. Thank you!

Upvotes: 0

Views: 137

Answers (2)

Elektito
Elektito

Reputation: 4155

I think this should work for you:

lista=[ ['a','b','c','d'],['b','f','g'],['c','h','i'],['d'],['h'],['i'],['f'],['g']]

def tree(root, d):
    return [root] + [tree(k, d) for k in d[root]]

d = {i[0]: i[1:] for i in lista}

root = 'a'
print(tree(root, d))

which prints this out:

['a', ['b', ['f'], ['g']], ['c', ['h'], ['i']], ['d']]

Although I believe the dictionary (d) itself might serve you better.

Upvotes: 0

Hugh Bothwell
Hugh Bothwell

Reputation: 56694

def nodeinline(head, nodes):
    return [head] + [nodeinline(child, nodes) for child in nodes.get(head, [])]

def nodebyref_to_nodeinline(lst):
    head  = lst[0][0]
    nodes = {node[0]: node[1:] for node in lst}
    return nodeinline(head, nodes)

nodebyref_to_nodeinline([['a','b','c','d'],['b','f','g'],['c','h','i'],['d'],['h'],['i'],['f'],['g']])

gives

['a', ['b', ['f'], ['g']], ['c', ['h'], ['i']], ['d']]

Upvotes: 2

Related Questions