necesita encontrar elemento hijo de la lista de python

tengo una lista de python como abajo

[(u'1', u'0'), (u'2', u'1'), (u'3', u'2'), (u'4', u'3'), (u'5', u'4'), (u'6', u'4'), (u'7', u'4'), (u'8', u'4'), (u'9', u'4'), (u'10', u'4'), (u'11', u'4'), (u'11.5', u'2'), (u'12', u'11.5'), (u'13', u'11.5'), (u'14', u'11.5'), (u'15', u'11.5'), (u'16', u'11.5'), (u'17', u'11.5'), (u'18', u'11.5'), (u'19', u'11.5'), (u'20', u'11.5'), (u'21', u'11.5'), (u'22', u'11.5'), (u'23', u'11.5'), (u'24', u'11.5'), (u'25', u'11.5'), (u'26', u'11.5'), (u'27', u'11.5'), (u'28', u'11.5'), (u'30', u'11.5'), (u'29', u'11.5')] 

aquí el primer lugar de cada tupla es su propia identificación, mientras que la segunda posición es su identificación principal.

Quiero obtener todos los hijos de identificación específica. Por ejemplo, si quiero obtener la lista de todos los selfies que son hijo (o hijo de niño … hasta la profundidad) de la propia ID “3”. así que la lista de respuestas será [u'4', u'5', u'6', u'7', u'8', u'9', u'10', u'11']

¿¿Alguna forma de hacer esto??

Puedes usar la librería networkx

 import networkx as nx g = nx.DiGraph() g.add_edges_from( (y,x) for x,y in your_list ) print list(nx.dfs_postorder_nodes(g, '3')) [u'11', u'10', u'5', u'7', u'6', u'9', u'8', u'4', '3'] 

Si no tienes un número definido de niveles …

Con tu lista li :

 d = {} for o, p in li: d.setdefault(p, []).append(o) todo = d[u'3'][:] descendants = [] while todo: node = todo.pop(0) todo.extend(d.get(node, [])) descendants.append(node) 

descendants contiene la lista buscada.

Si la relación no cambia a menudo, una solución es construir el cierre transitivo, por lo tanto:

 def tclose(data): data = set(data) while True: new = set( (a, d) for (a, b) in data for (c, d) in data if b == c ) - data if not new: return data data.update(new) data = tclose([(u'1', u'0'), …]) 

Entonces puedes localizar descendientes, así:

 descendants = set( d for (d, a) in data if a == '3' ) 

Si desea limitar la búsqueda a una profundidad fija, puede reemplazar while True con for _ in range(n - 1) . Si n varía, necesitarás una solución diferente.

Tenga en cuenta que esta solución se centra en la simplicidad. No es el algoritmo más rápido posible, y podría necesitar rehabilitación si le da un conjunto de entrada grande.

 from collections import defaultdict mylist = [(u'1', u'0'), (u'2', u'1'), (u'3', u'2'), (u'4', u'3'), (u'5', u'4'), (u'6', u'4'), (u'7', u'4'), (u'8', u'4'), (u'9', u'4'), (u'10', u'4'), (u'11', u'4'), (u'11.5', u'2'), (u'12', u'11.5'), (u'13', u'11.5'), (u'14', u'11.5'), (u'15', u'11.5'), (u'16', u'11.5'), (u'17', u'11.5'), (u'18', u'11.5'), (u'19', u'11.5'), (u'20', u'11.5'), (u'21', u'11.5'), (u'22', u'11.5'), (u'23', u'11.5'), (u'24', u'11.5'), (u'25', u'11.5'), (u'26', u'11.5'), (u'27', u'11.5'), (u'28', u'11.5'), (u'30', u'11.5'), (u'29', u'11.5')] def make_tree(lst): """ Accepts a list of (item, parent) Returns a dict of parent:[children] """ res = defaultdict(list) for child,parent in lst: res[parent].append(child) return res def find_children(tree, root, max_depth=-1): """ Accepts a dict of parent:[children] Returns a recursive list of (child, [children_of_child]) of root to the given maximum depth (if max_depth is negative, recursion is not limited) """ if max_depth and (root in tree): return [(child, find_children(tree, child, max_depth-1)) for child in tree[root]] else: return [] def flatten(ans): """ Accepts a recursive list Returns a flat list of nodes """ res = [] for parent,children in ans: res.append(parent) res.extend(flatten(children)) return res print flatten(find_children(build_tree(mylist), u'3', 4)) 

resultados en

 [u'4', u'5', u'6', u'7', u'8', u'9', u'10', u'11']