Поиск максимальной глубины набора в словаре

Question

У меня есть словарь, где ключ является строкой, а значения ключа представляют собой набор строк, которые также содержат ключ (цепочка слов). У меня возникли проблемы с поиском максимальной глубины графа, который был бы множеством с большинством элементов в словаре, и я попробую распечатать этот макс граф.

Прямо сейчас мой код печатает:

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

Где 1 моя максимальная глубина словаря. Я ожидал, что глубина будет равна двум, но, по-видимому, на графике «POT» есть только 1 слой

Как найти максимальное значение, заданное из набора ключей в словаре?

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 

Answer 1

«Глубина» словаря, естественно, будет 1 плюс максимальная глубина его записей. Вы определили глубину не-словаря равной нулю. Поскольку ваш словарь верхнего уровня не содержит ни одного словаря, глубина словаря явно 1. Ваша функция сообщает, что значение правильно.

Однако ваша функция не написана в ожидании формата данных, который вы предоставляете. Мы можем легко найти входы, где глубина цепочек подстрок больше, чем одна. Например:

 
DOG 
DOGMA 
DOGMATIC 
DOGHOUSE 
POT 

Выход из текущего сценария:

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

Я думаю, что вы хотите получить 2 для этого входа, так как самая длинная подстрока цепь DOG → Догма → ДОГМАТИЧЕСКОЙ, который содержит два хмеля.

Чтобы получить глубину словаря, как вы его структурировали, вы хотите рассчитать длину цепи для каждого слова. Это один плюс максимальная длина цепи каждого из ее подстрок, что дает нам следующие две функции:

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 функция, заданная здесь не особенно эффективен. Это может закончиться вычислением длин одной цепочки несколько раз, если строка является подстрокой многих слов. Динамическое программирование - это простой способ смягчить это, что я оставлю как упражнение.

Answer 2

К сожалению моих примеры не будут в питоне, потому что мой питон ржавый, но вы должны получить идею.

Допустим, это бинарное дерево:
(написанный на C++)

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

Simple. Теперь давайте расширим это слишком много, а затем просто слева и справа.
(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 к каждому уровню при обходе.