472,992 Members | 3,578 Online

# Retrieving indexes of elements in a nested list by recursive depth

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:
Expand|Select|Wrap|Line Numbers
1. def getChildrenNodes2(lst,depth):
2.     result=[]
3.     if depth>0:
4.         for elem in getChildrenNodes2(lst,depth-1):
5.             if isinstance(elem, list):
6.                 result.extend(elem[1:])
7.     else:
8.         result =lst
9.     return result
10.
But this is not the same as giving indexes of all elements at depth n...
Any idea would really be welcomed!
Cheers!
Jul 29 '07 #1
2 11140
bartonc
6,596 Expert 4TB
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:
Expand|Select|Wrap|Line Numbers
1. def getChildrenNodes2(lst,depth):
2.     result=[]
3.     if depth>0:
4.         for elem in getChildrenNodes2(lst,depth-1):
5.             if isinstance(elem, list):
6.                 result.extend(elem[1:])
7.     else:
8.         result =lst
9.     return result
10.
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:
Expand|Select|Wrap|Line Numbers
1. >>> A, B, D, H, I, E, C, F, G = range(9)
2. >>> tree = [A, [B, [D, H, I], E], [C, F, G]]
3. >>> tree.index([B, [D, H, I], E])
4. 1
5. >>> tree[1].index([D, H, I])
6. 1
7. >>>
Jul 29 '07 #2
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).
Expand|Select|Wrap|Line Numbers
1. def bill_subtree_indices( tree_rep ,depth):
2.     q = [ ([],tree_rep) ]
3.     list_of_index_lists = []
4.     while q != []:
5.         (indices, sub_tree) = q.pop(0)
6.         list_of_index_lists.append(indices)
7.         if len(indices)==depth+1:
8.             list_of_index_lists.pop()
9.             return list_of_index_lists
10.         for (ordinal, sst) in enumerate( sub_tree[1:] ):
11.             if isinstance( sst, list ):
12.                 idxs = indices[:]
13.                 idxs.append(ordinal+1)
14.                 q.append( (idxs, sst) )
15.     return list_of_index_lists
16.
It gives the following results:
Expand|Select|Wrap|Line Numbers
1. >>> bill_subtree_indices([1,[2,[3,4,[5,6,7]]],[8,[9,10,11]],[12,[13,[14,[15,16]]]]],3)
2. [[], [1], [2], [3], [1, 1], [2, 1], [3, 1], [1, 1, 2], [3, 1, 1]]
3. >>> bill_subtree_indices([1,[2,[3,4,[5,6,7]]],[8,[9,10,11]],[12,[13,[14,[15,16]]]]],2)
4. [[], [1], [2], [3], [1, 1], [2, 1], [3, 1]]
5. >>> bill_subtree_indices([1,[2,[3,4,[5,6,7]]],[8,[9,10,11]],[12,[13,[14,[15,16]]]]],1)
6. [[], [1], [2], [3]]
7.
Cheers!
Jul 29 '07 #3