查找字典中的集合的最大深度

我有一个字典，其中的关键字是一个字符串，而关键字的值是一组也包含关键字（字链）的字符串。我无法找到图表的最大深度，这是字典中元素最多的集合，我也尝试打印出最大图表。查找字典中的集合的最大深度

现在我的代码打印：

{'DOG': [], 
'HIPPOPOTIMUS': [], 
'POT': ['SUPERPOT', 'HIPPOPOTIMUS'], 
'SUPERPOT': []} 
1

其中1是我最大的字典深度。我期待的深度是两个，但似乎只有1层'POT'的图形

如何从字典中的键集中找到最大值集？

import pprint 

def dict_depth(d, depth=0): 
    if not isinstance(d, dict) or not d: 
     return depth 
    print max(dict_depth(v, depth+1) for k, v in d.iteritems()) 


def main(): 
    for keyCheck in wordDict: 
     for keyCompare in wordDict: 
      if keyCheck in keyCompare: 
       if keyCheck != keyCompare: 
        wordDict[keyCheck].append(keyCompare) 

if __name__ == "__main__": 
    #load the words into a dictionary 
    wordDict = dict((x.strip(), []) for x in open("testwordlist.txt")) 
    main() 
    pprint.pprint (wordDict) 
    dict_depth(wordDict)

testwordlist.txt：

POT 
SUPERPOT 
HIPPOPOTIMUS 
DOG

来源

2015-10-12 Simmeringc

http：// stackoverflow。com/questions/9538875 /递归深度的python-dictionary https://www.google.ca/search?q=python+max+depth+of+a+set+in+a+dictionary&ie=utf-8&oe = utf-8＆gws_rd = cr＆ei = UwscVq6PK8HReo3BsvAI – BAE

字典的“深度”自然会为1加上其条目的最大深度。您已将非字典的深度定义为零。由于您的顶级字典不包含任何自己的字典，因此字典的深度显然为1.您的函数正确报告了该值。

但是，您的函数并没有写入您期望提供的数据格式。我们可以很容易地提出输入，其中子串链的深度不止一个。例如：

 
DOG 
DOGMA 
DOGMATIC 
DOGHOUSE 
POT

您当前脚本的输出：

 
{'DOG': ['DOGMATIC', 'DOGMA', 'DOGHOUSE'], 
'DOGHOUSE': [], 
'DOGMA': ['DOGMATIC'], 
'DOGMATIC': [], 
'POT': []} 
1

我想你想拿到2为输入，因为最长的串链DOG→教条→教条化，其中包含两周跳。

为了得到字典深度的结构，你需要计算每个单词的链长。这是1加它的每个子的最大链长，这给了我们以下两个功能：

def word_chain_length(d, w): 
    if len(d[w]) == 0: 
     return 0 
    return 1 + max(word_chain_length(d, ww) for ww in d[w]) 

def dict_depth(d): 
    print(max(word_chain_length(d, w) for w in d))

这里给出的word_chain_length功能不是特别有效。如果一个字符串是多个单词的子字符串，它最终可能会多次计算相同链的长度。 动态编程是一种简单的方法来减轻这一点，我将作为练习离开。

来源

2015-10-12 20:12:25

非常感谢，对于链长度与字典中“图形”深度之间的差异，我仍有点困惑。字典的最大深度是1，因为没有嵌套键，但不应该最大链是4？ DOG - > DOGMATIC - > DOGMA - > DOGHOUSE – Simmeringc

对不起我的例子不会是蟒蛇，因为我的Python是生锈，但你应该明白我的意思。

让我们说这是一个二叉树：
（用C++）

int depth(TreeNode* root){ 
    if(!root) return 0; 
    return 1+max(depth(root->left), depth(root->right)); 
}

简单。现在让我们把它扩展得更多，然后只是左右两边。
（golang代码）

func depthfunc(Dic dic) (int){ 
    if dic == nil { 
    return 0 
    } 
    level := make([]int,0) 
    for key, anotherDic := range dic{ 
     depth := 1 
     if ok := anotherDic.(Dic); ok { // check if it does down further 
     depth = 1 + depthfunc(anotherDic) 
     } 
     level = append(level, depth)   
    } 

    //find max 
    max := 0 
    for _, value := range level{ 
    if value > max { 
     max = value 
    } 
    } 
    return max 
}

的想法是，你刚才下去的每个字典，直到有没有更多的字典下井加1，你遍历每个级别。

来源

2015-10-12 19:11:29 Jay

查找字典中的集合的最大深度

回答

相关问题