4

我有一个如下的python列表

[(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')]

这里每个元组的第 1 个位置是它自己的 id，而第 2 个位置是它的父 id。

我想得到特定ID的所有孩子。例如，如果我想获取所有自己的 ID 为“3”的孩子（或孩子的孩子......到 n 深度）的列表。所以答案列表将是[u'4', u'5', u'6', u'7', u'8', u'9', u'10', u'11']

有什么办法可以做到这一点？？

4

4 回答 4

5

你可以使用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']
于 2012-07-12T12:25:48.697 回答
2

如果您没有定义的级别数……</p>

用你的清单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包含搜索的列表。

于 2012-07-12T11:52:23.423 回答
1

如果关系不经常改变，一种解决方案是构建传递闭包，因此：

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'), …])

然后你可以找到后代，因此：

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

如果要将搜索限制在固定深度，可以替换while True为for _ in range(n - 1). 如果n有所不同，您将需要不同的解决方案。

请注意，此解决方案侧重于简单性。它不是最快的算法，如果你给它一个大的输入集，可能需要修复。

于 2012-07-12T12:06:18.903 回答
0 
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))

结果是

[u'4', u'5', u'6', u'7', u'8', u'9', u'10', u'11']
于 2012-07-12T13:00:20.600 回答