8

attrsを持つ要素のリストがあります：parent、level、is_leaf_node、is_root_node、is_child_node。

このリストを階層辞書に変換したいと思います。出力dictの例：

{
        'Technology':
            {
             'Gadgets':{},
             'Gaming':{},
             'Programming':
                {
                    'Python':{},
                    'PHP':{},
                    'Ruby':{},
                    'C++':{}
                },
             'Enterprise':{},
             'Mac':{},
             'Mobile':{},
             'Seo':{},
             'Ui':{},
             'Virtual Worlds':{},
             'Windows':{},
            },
        'News':{
            'Blogging':{},
            'Economics':{},
            'Journalism':{},
            'Politics':{},
            'News':{}
            },}

アルゴリズムがわかりません。どうやってするの？

4

5 に答える 5

12

これは、chmod 700 のような洗練されていない再帰的なバージョンです。もちろん完全にテストされていません：

def build_tree(nodes):
    # create empty tree to fill
    tree = {}

    # fill in tree starting with roots (those with no parent)
    build_tree_recursive(tree, None, nodes)

    return tree

def build_tree_recursive(tree, parent, nodes):
    # find children
    children  = [n for n in nodes if n.parent == parent]

    # build a subtree for each child
    for child in children:
        # start new subtree
        tree[child.name] = {}

        # call recursively to build a subtree for current node
        build_tree_recursive(tree[child.name], child, nodes)
于 2009-04-16T19:02:37.057 に答える
2

親のないものはすべてトップ レベルなので、最初にそれらのディクテーションを作成します。次に、配列を介して2回目のパスを実行して、その最上位に親を持つすべてのものを見つけます。ループまたは再帰関数として記述できます。「親」以外に提供された情報は本当に必要ありません。

于 2009-04-16T18:13:53.040 に答える
2

基本的にやりたいことは、トポロジカルソートの変形です。このための最も一般的なアルゴリズムは、ソース削除アルゴリズムです。擬似コードは次のようになります。

import copy
def TopSort(elems): #elems is an unsorted list of elements.
    unsorted = set(elems)
    output_dict = {}
    for item in elems:
        if item.is_root():
            output_dict[item.name] = {}
            unsorted.remove(item)
            FindChildren(unsorted, item.name, output_dict[item.name])
    return output_dict

def FindChildren(unsorted, name, curr_dict):
    for item in unsorted:
        if item.parent == name:
            curr_dict[item.name] = {}
            #NOTE:  the next line won't work in Python.  You
            #can't modify a set while iterating over it.
            unsorted.remove(item)
            FindChildren(unsorted, item.name, curr_dict[item.name])

これは明らかにいくつかの場所で壊れています (少なくとも実際の Python コードとして)。ただし、アルゴリズムがどのように機能するかについてのアイデアが得られることを願っています。あなたが持っているアイテムにサイクルがある場合、これはひどく失敗することに注意してください（たとえば、アイテムaには親としてアイテムbがあり、アイテムbには親としてアイテムaがあります）。しかし、とにかくやりたい形式で表現することはおそらく不可能でしょう。

于 2009-04-16T18:42:00.333 に答える
0

このような単純なものがうまくいくかもしれません:

def build_tree(category_data):
  top_level_map = {}
  cat_map = {}
  for cat_name, parent, depth in cat_data:
    cat_map.setdefault(parent, {})
    cat_map.setdefault(cat_name, {})
    cat_map[parent][cat_name] = cat_map[cat_name]
    if depth == 0:
      top_level_map[cat_name] = cat_map[cat_name]

  return top_level_map
于 2009-04-17T01:05:37.637 に答える