By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,035 Members | 1,984 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,035 IT Pros & Developers. It's quick & easy.

Retrieving indexes of elements in a nested list by recursive depth

P: 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
Share this Question
Share on Google+
2 Replies


bartonc
Expert 5K+
P: 6,596
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

P: 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.