471,310 Members | 1,018 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,310 software developers and data experts.

Retrieving indexes of elements in a nested list by recursive depth

2
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 10810
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
Gentr1
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

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

2 posts views Thread by rankam | last post: by
9 posts views Thread by Csaba Gabor | last post: by
19 posts views Thread by George Sakkis | last post: by
9 posts views Thread by pereges | last post: by
reply views Thread by rosydwin | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.