पेड़ सूची को पदानुक्रम में कनवर्ट करना

Question

मेरे पास attrs के साथ तत्वों की एक सूची है: अभिभावक, स्तर, is_leaf_node, is_root_node, is_child_node है।

मैं इस सूची को पदानुक्रमित dict में परिवर्तित करना चाहता हूं। उत्पादन dict की उदाहरण:

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

मैं एल्गोरिथ्म पता नहीं है। यह कैसे करना है?

Answer 1

यहां एक कम परिष्कृत, रिकर्सिव संस्करण है जैसे कि 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) 

Answer 2

माता-पिता के बिना सबकुछ आपका शीर्ष स्तर है, इसलिए उन डिक्ट्स को पहले बनाएं। फिर उस शीर्ष स्तर पर माता-पिता के साथ सबकुछ ढूंढने के लिए अपने सरणी के माध्यम से दूसरा पास करें ... इसे लूप या रिकर्सिव फ़ंक्शन के रूप में लिखा जा सकता है। आपको वास्तव में "माता-पिता" के अलावा प्रदान की गई किसी भी जानकारी की आवश्यकता नहीं है।

Answer 3

ऐसा लगता है कि आप मूल रूप से करना चाहते हैं topological sorting का एक संस्करण है। इसके लिए सबसे आम एल्गोरिदम स्रोत हटाने एल्गोरिदम है।

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]) 

यह स्पष्ट रूप से स्थानों के एक जोड़े में टूट गया है (कम से कम वास्तविक अजगर कोड के रूप में): स्यूडोकोड कुछ इस तरह दिखेगा। हालांकि, उम्मीद है कि जो आपको इस बारे में एक विचार देगा कि एल्गोरिदम कैसे काम करेगा। ध्यान दें कि यदि आपके पास मौजूद वस्तुओं में कोई चक्र है तो यह बहुत ही असफल हो जाएगा (आइटम कहें कि आइटम में माता-पिता के रूप में आइटम बी है जबकि आइटम बी में माता-पिता के रूप में आइटम है)। लेकिन फिर उस प्रारूप में प्रतिनिधित्व करना असंभव होगा जिसे आप वैसे भी करना चाहते हैं।

Answer 4

कुछ इस तरह साधारण काम कर सकते हैं:

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 

Answer 5

एक अच्छा पुनरावर्ती तरह से यह करने के लिए:

def build_tree(elems): 
    elem_with_children = {} 

    def _build_children_sub_tree(parent): 
     cur_dict = { 
      'id': parent, 
      # put whatever attributes here 
     } 
     if parent in elem_with_children.keys(): 
      cur_dict["children"] = [_build_children_sub_tree(cid) for cid in elem_with_children[parent]] 
     return cur_dict 

    for item in elems: 
     cid = item['id'] 
     pid = item['parent'] 
     elem_with_children.setdefault(pid, []).append(cid) 

    res = _build_children_sub_tree(-1) # -1 is your root 
    return res