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,depth1):

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!
2 10810
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,depth1):

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

>>>
The problem was actually to find the "path" of indexes until a certain depth.
Luckily, some guru from pythonforum.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!
Post your reply Sign in to post your reply or Sign up for a free account.
Similar topics
1 post
views
Thread by Chris P. 
last post: by

2 posts
views
Thread by Christopher 
last post: by

2 posts
views
Thread by rankam 
last post: by

10 posts
views
Thread by BCC 
last post: by

14 posts
views
Thread by BQ 
last post: by

12 posts
views
Thread by coosa 
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
          