creating "data tree" paths recursively iterating over nested lists in python

1.2k views Asked by At

I am trying to create a list of "paths" to every item within a _list. for example input list:

_list = [[x,x,x], [[x,x,x],[x,x,x]], [x,x,x]]

desired output:

_list = [\
        [[0,0,0],[0,0,0],[0,0,0]], \
        [[[0,1,0],[0,1,0],[0,1,0]],[[0,1,1],[0,1,1],[0,1,1]]] \ 
        [[0,2,0], [0,2,0], [0,2,0]]]

the idea is that i am creating a path to a data tree similar to this:

http://studiomaven.org/images/2/2c/Grasshopper_Data_Tree.png

where first branch is 0. then since _list has three(3) lists in it then first second level branches are [0,0][0,1] and [0,2] then since [0,1] branch has one more list in it then another level has to be added where all items in first branch are [0,0,0], second are [0,1,0] and [0,1,1] since there are two lists in that branch and then final branch is [0,2,0].

Example 2:Input:

_list = [x,x,x,x]

Output:

_list = [[0],[0],[0],[0]]

Explanation: Since its a single depth list all information resides on the first [0] branch. Every item x has a path [0]

Example 3: Input:

_list = [[x,x,x],[x,x,x]]

Output:

_list = [[[0,0],[0,0],[0,0]],[[0,1],[0,1],[0,1]]]

Explanation: _List contains two lists so first branch 0 has two more branches on it. In that case all items on that level two branch are [0,0] and on the second branch [0,1].

can this be done recursively in some manner that will work on any depth/complexity of list of lists?

I understand that this is not a bug/issue, but I am a bit of a noob and recursive functions are still a mystery to me. Any help will be much appreciated. Even simple pseudo code to get me started. thank you,

1

There are 1 answers

1
user_num_9 On

You can try and create a class for a general tree and have the various branches as children of the root object. Say the root object can be of value 0, then the leftmost child will be of value [0,0], the next child of value [0,1] and so on. If the child is a nested list, then you can create a method to make further children out of this and add them to the initial node as their parent. You can initialise the class as something like this and can work accordingly,

class GrassTree():

    def __init__(self, lst):
        self.key = "0"
        self.child = []
        for i in lst:
            self.child.append(i)

    def getChild(self):
        for i in range(0, len(self.child)):
            print(self.child[i])

This is just a skeletal thing and an idea that i have started to work with in order to solve this question. Will work on it further. As far as recursion goes, it will come into picture when one tries to implement classes to insert children.

PS: Could have given just a comment for this but didn't have enough reputation to do so, thus such a naive answer. Sorry for that.