Как использовать словарь словарей в качестве вывода из Python?

Question

Эта функция сводит меня с ума!

def CCAD1 (tree)
    leaves = []
    for otu in tree:
        if tree[otu][2]== None and tree[otu][1]== None:
                leaves += [otu]
    ccad = {}
    for leaf in leaves:
            otuX = leaf
            otu1 = leaf
            for leaf2 in leaves:
                otuY = leaf2
                otu2 = leaf2
                while tree[otu1][0] is not None and tree[otu2][0] is not None and tree[otu1][0][0] != tree[otu2][0][0]:
                        otu1,otu2,tree = tree[otu1][0][0],tree[otu2][0][0],tree
                if tree[otu1][0] is not None:
                    ccad[otuX] = {otuY:tree[otu1][0]}
    return ccad

Это входные данные для функции

{'A': [('AD', 4.0), None, None], 'C': [('ADBFGC', 14.5), None, None], 'B': [('BF', 0.5), None, None], 'E': [('ADBFGCE', 17.0), None, None], 'D': [('AD', 4.0), None, None], 'G': [('BFG', 6.25), None, None], 'F': [('BF', 0.5), None, None], 'ADBFG': [('ADBFGC', 6.25), ('AD', 4.25), ('BFG', 2.0)], 'BF': [('BFG', 5.75), ('B', 0.5), ('F', 0.5)], 'ADBFGC': [('ADBFGCE', 2.5), ('ADBFG', 6.25), ('C', 14.5)], 'ADBFGCE': [None, ('ADBFGC', 2.5), ('E', 17.0)], 'BFG': [('ADBFG', 2.0), ('BF', 5.75), ('G', 6.25)], 'AD': [('ADBFG', 4.25), ('A', 4.0), ('D', 4.0)]}

Выходные данные должны иметь структуру, похожую на {"A":{"B":("AB",4)}}, вкод выше это словарь «CCAD».Я буквально всю ночь пытался сделать это, но это не работает, и я понятия не имею, почему.

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

Он выводит словарь словарей, который мне нужен, но он не делает это для каждой пары, только для определенных.«Древовидная» структура данных также находится в этой ссылке, если вам нужно ее увидеть.

Любая помощь приветствуется, на этом этапе я очень отчаялся: /

Answer 1

Хорошо, я думаю, вы хотите рассчитать расстояния между каждым узлом листа. Поэтому я стараюсь решить вашу проблему, а не отвечать на ваш вопрос.

Ваш алгоритм commonAncestor имеет недостатки, так как предполагает, что все конечные узлы имеют одинаковую глубину. Это не так.

Первое решение, которое приходит на ум, - определить все конечные узлы и рассчитать путь к корневому узлу для каждого из них. Определите ближайшего общего предка, сравнив оба пути в обратном порядке.

Выходные данные - это словарь пар узлов и количество прыжков между ними.

from itertools import combinations

data = {'A': [('AD', 4.0), None, None], 'C': [('ADBFGC', 14.5), None, None], 'B': [('BF', 0.5), None, None], 'E': [('ADBFGCE', 17.0), None, None], 'D': [('AD', 4.0), None, None], 'G': [('BFG', 6.25), None, None], 'F': [('BF', 0.5), None, None], 'ADBFG': [('ADBFGC', 6.25), ('AD', 4.25), ('BFG', 2.0)], 'BF': [('BFG', 5.75), ('B', 0.5), ('F', 0.5)], 'ADBFGC': [('ADBFGCE', 2.5), ('ADBFG', 6.25), ('C', 14.5)], 'ADBFGCE': [None, ('ADBFGC', 2.5), ('E', 17.0)], 'BFG': [('ADBFG', 2.0), ('BF', 5.75), ('G', 6.25)], 'AD': [('ADBFG', 4.25), ('A', 4.0), ('D', 4.0)]}

def get_path(tree,leaf):
  path = []
  location = leaf
  while True:
    path.append(location)
    parent = tree.get(location)[0]
    if parent:
      location = parent[0]
    else:
      break
  return path

def get_leaves(tree):
  return [ x for (x,y) in tree.items() if y[1] is None and y[2] is None ]

def leafDistances(tree):
  paths = {}
  leaves = get_leaves(tree)
  for leaf in leaves:
    paths[leaf] = get_path(tree,leaf)
  results = {}
  for l1,l2 in combinations(leaves,2):
    commonAncestor = [ x for (x,y) in zip(paths[l1][::-1],paths[l2][::-1]) if x == y ][-1]
    distance = paths[l1].index(commonAncestor) + paths[l2].index(commonAncestor)
    results[(l1,l2)] = distance
    print "%s <-> %s Ancestor == %s, distance == %s\nPath of %s == %s\nPath of %s == %s" % (l1,l2,commonAncestor,distance,l1,paths[l1],l2,paths[l2])
  return results

leafDistances(data)

Это напечатано для ясности:

A <-> C Ancestor == ADBFGC, distance == 4
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
A <-> B Ancestor == ADBFG, distance == 5
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
A <-> E Ancestor == ADBFGCE, distance == 5
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of E == ['E', 'ADBFGCE']
A <-> D Ancestor == AD, distance == 2
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
A <-> G Ancestor == ADBFG, distance == 4
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
A <-> F Ancestor == ADBFG, distance == 5
Path of A == ['A', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
C <-> B Ancestor == ADBFGC, distance == 5
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
C <-> E Ancestor == ADBFGCE, distance == 3
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
Path of E == ['E', 'ADBFGCE']
C <-> D Ancestor == ADBFGC, distance == 4
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
C <-> G Ancestor == ADBFGC, distance == 4
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
C <-> F Ancestor == ADBFGC, distance == 5
Path of C == ['C', 'ADBFGC', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
B <-> E Ancestor == ADBFGCE, distance == 6
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of E == ['E', 'ADBFGCE']
B <-> D Ancestor == ADBFG, distance == 5
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
B <-> G Ancestor == BFG, distance == 3
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
B <-> F Ancestor == BF, distance == 2
Path of B == ['B', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
E <-> D Ancestor == ADBFGCE, distance == 5
Path of E == ['E', 'ADBFGCE']
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
E <-> G Ancestor == ADBFGCE, distance == 5
Path of E == ['E', 'ADBFGCE']
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
E <-> F Ancestor == ADBFGCE, distance == 6
Path of E == ['E', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
D <-> G Ancestor == ADBFG, distance == 4
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
D <-> F Ancestor == ADBFG, distance == 5
Path of D == ['D', 'AD', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
G <-> F Ancestor == BFG, distance == 3
Path of G == ['G', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']
Path of F == ['F', 'BF', 'BFG', 'ADBFG', 'ADBFGC', 'ADBFGCE']

Answer 2

Поскольку вы не дали желаемый результат, отладку кода довольно сложно, но у меня есть ощущение, что последнее условие if должно быть под while.