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) であるすべての ownids のリストを取得したい場合。回答リストは[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

関係が頻繁に変更されない場合、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 に答える