Retrieving indexes of elements in a nested list by recursive depth

[Gentr1]

Hi everybody!

I am presently working on a Genetic Programming API in python.
I have a bit of a problem at the moment...
For some specific reasons, I am using nested lists data structure to represent a tree. The first element of a list is always the head of the node, while all others represent the tail of the node.
e.g. the nested list [A, [B, [D, H, I], E], [C, F, G]] represent the following tree:

I need to be able to choose at random a sub tree at a given depth, in order to swap it with another subtree coming from a different tree.
So, I really need to know the index of all subtrees at depth n.
I have come up with a small program that gives all elements in a nested list for a given depth:

def getChildrenNodes2(lst,depth):
    result=[]
    if depth>0:
        for elem in getChildrenNodes2(lst,depth-1):
            if isinstance(elem, list):
                result.extend(elem[1:])
    else:
        result =lst
    return result
 

But this is not the same as giving indexes of all elements at depth n...
Any idea would really be welcomed!
Cheers!

[bartonc]

Hi everybody!

I am presently working on a Genetic Programming API in python.
I have a bit of a problem at the moment...
For some specific reasons, I am using nested lists data structure to represent a tree. The first element of a list is always the head of the node, while all others represent the tail of the node.
e.g. the nested list [A, [B, [D, H, I], E], [C, F, G]] represent the following tree:

I need to be able to choose at random a sub tree at a given depth, in order to swap it with another subtree coming from a different tree.
So, I really need to know the index of all subtrees at depth n.
I have come up with a small program that gives all elements in a nested list for a given depth:

def getChildrenNodes2(lst,depth):
    result=[]
    if depth>0:
        for elem in getChildrenNodes2(lst,depth-1):
            if isinstance(elem, list):
                result.extend(elem[1:])
    else:
        result =lst
    return result
 

But this is not the same as giving indexes of all elements at depth n...
Any idea would really be welcomed!
Cheers!

It's interesting that your list structure doesn't accurately represent your tree, as it is shown.

An index can be retrieved:

>>> A, B, D, H, I, E, C, F, G = range(9)
>>> tree = [A, [B, [D, H, I], E], [C, F, G]]
>>> tree.index([B, [D, H, I], E])
1
>>> tree[1].index([D, H, I])
1
>>> 

[Gentr1]

The problem was actually to find the "path" of indexes until a certain depth.
Luckily, some guru from python-forum.org (named Bill) came up with the following solution (I just added the depth stopping condition to his code).

def bill_subtree_indices( tree_rep ,depth):
    q = [ ([],tree_rep) ]
    list_of_index_lists = []
    while q != []:  
        (indices, sub_tree) = q.pop(0)
        list_of_index_lists.append(indices)
        if len(indices)==depth+1:
            list_of_index_lists.pop()
            return list_of_index_lists
        for (ordinal, sst) in enumerate( sub_tree[1:] ):
            if isinstance( sst, list ):
                idxs = indices[:]
                idxs.append(ordinal+1)
                q.append( (idxs, sst) )
    return list_of_index_lists
 

It gives the following results:

>>> bill_subtree_indices([1,[2,[3,4,[5,6,7]]],[8,[9,10,11]],[12,[13,[14,[15,16]]]]],3)
[[], [1], [2], [3], [1, 1], [2, 1], [3, 1], [1, 1, 2], [3, 1, 1]]
>>> bill_subtree_indices([1,[2,[3,4,[5,6,7]]],[8,[9,10,11]],[12,[13,[14,[15,16]]]]],2)
[[], [1], [2], [3], [1, 1], [2, 1], [3, 1]]
>>> bill_subtree_indices([1,[2,[3,4,[5,6,7]]],[8,[9,10,11]],[12,[13,[14,[15,16]]]]],1)
[[], [1], [2], [3]]
 

Cheers!