Вычислить вероятности в вероятностном дереве

Question

У меня есть следующий словарь:

dict = {1000021: [[0.6, [1000024, 1, -2]], [0.4, [1000022, 21]]], 
     1000024: [[0.7, [1000022, 11, -12]], [0.3, [1000022, 2, -1]]]} 

, который соответствует следующему вероятностному дереву:

Начиная с 1000021, я теперь нужен рассчитать все вероятности и список чисел, которые я получаю для каждой возможной конечной точки. Всякий раз, когда есть номер со словарной записью, мне нужно следовать этому пути. Словарь может иметь случайное количество записей и случайное число подписок. Желаемый выход:

[0.4, [1000022, 21]], 
[0.42, [1000022, 11, -12, 1, -2]], 
[0.18, [1000022, 2, -1, 1, -2] 

Я попытался сделать это с помощью рекурсивной функции, но безрезультатно. Любая помощь приветствуется.

Edit:

я был не ясно, в моем первом примере, так как может привести к предположению, что только первый элемент в подсписке может иметь словарную статью, в то время как все они на самом деле может иметь один. Ответ, данный Copperfield, работает для примера выше, но он не работает, например.

mydata = {1: [[.9, [2,3]], [.1, [4,5]]], 
      4: [[.2, [6,7]], [.5, [8,9]], [.3, [10,11,12]]], 
      5: [[.4, [13,14]], [.6, [15,16]]]} 

где я ожидаю, что выход будет:

[0.9, [2, 3]], 
[0.008, [6, 7, 13, 14]], 
[0.012, [6, 7, 15, 16]], 
[0.02, [8, 9, 13, 14]], 
[0.03, [8, 9, 15, 16]], 
[0.012, [10, 11, 12, 13, 14]], 
[0.018, [10, 11, 12, 15, 16]] 

Answer 1

, что далеко от дерева, но как об этом

import copy 

mydata = {1000024: [[0.7, [1000022, 11, -12]], [0.3, [1000022, 2, -1]]], 
      1000021: [[0.6, [1000024, 1, -2]], [0.4, [1000022, 21]]]} 

def prob_tree(data,ini,prob=1): 
    data=copy.deepcopy(data) 
    val=data.pop(ini,None) 
    if val: 
     for lst in val: 
      if lst[1][0] in data: 
       extra=lst[1][1:] 
       for x in data[lst[1][0]]: 
        x[1].extend(extra) 
       prob_tree(data,lst[1][0],lst[0]) 
      else: 
       print(prob*lst[0],lst[1]) 

prob_tree(mydata,1000021) 

выход

0.42 [1000022, 11, -12, 1, -2] 
0.18 [1000022, 2, -1, 1, -2] 
0.4 [1000022, 21] 

EDIT

В вдохновение ударил и использование небольшого функционального стиля здесь новая версия

import itertools, functools 

def partition(pred, iterable): 
    'Use a predicate to partition entries into false entries and true entries' 
    # partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9 
    # Direct from the recipes in itertools documentation 
    t1, t2 = itertools.tee(iterable) 
    return itertools.filterfalse(pred, t1), filter(pred, t2) 


def prob_tree(data,ini) -> (float,tuple): 
    """Generator of all end points of the probability tree contained 
     in data, starting with ini""" 
    for prob,path in data[ini]: 
     no_more,more = map(tuple,partition(lambda x: x in data, path)) 
     if more: 
      for node in itertools.product(*[prob_tree(data,x) for x in more]): 
       new_prob,new_path = functools.reduce(lambda acum,new: (acum[0]*new[0],acum[1]+new[1]),node,(prob,tuple())) 
       yield new_prob, no_more + new_path 
     else: 
      yield prob, no_more 

mydata = {1: [[.9, [2,3]], [.1, [4,5]]], 
      4: [[.2, [6,7]], [.5, [8,9]], [.3, [10,11,12]]], 
      5: [[.4, [13,14]], [.6, [15,16]]] 
      } 

mydata2 = {1: [[.8, [2,3]], [.1, [4,5]],[.05, [2,4]],[.05,[5,6]] ], 
      4: [[.2, [6,7]], [.5, [8,9]], [.3, [10,11,12]]], 
      5: [[.4, [13,14]], [.6, [15,16]]] 
      } 

mydata3 = {1: [[.8, [2,3]], [.1, [4,5]],[.05, [2,4]],[.05,[5,6]] ], 
      4: [[.2, [6,7]], [.5, [8,9]], [.3, [10,11,12]]], 
      5: [[.4, [13,14]], [.6, [15,16]]], 
      13:[[.58,[23,32]],[.42,[42]] ], 
      16:[ [.9,[17,18]], [.1,[20,21]] ], 
      } 

выход

>>> for x in prob_tree(mydata,1): 
    print(x) 


(0.9, (2, 3)) 
(0.008000000000000002, (6, 7, 13, 14)) 
(0.012000000000000002, (6, 7, 15, 16)) 
(0.020000000000000004, (8, 9, 13, 14)) 
(0.03, (8, 9, 15, 16)) 
(0.012, (10, 11, 12, 13, 14)) 
(0.018, (10, 11, 12, 15, 16)) 
>>> 
>>> 
>>> for x in prob_tree(mydata2,1): 
    print(x) 


(0.8, (2, 3)) 
(0.008000000000000002, (6, 7, 13, 14)) 
(0.012000000000000002, (6, 7, 15, 16)) 
(0.020000000000000004, (8, 9, 13, 14)) 
(0.03, (8, 9, 15, 16)) 
(0.012, (10, 11, 12, 13, 14)) 
(0.018, (10, 11, 12, 15, 16)) 
(0.010000000000000002, (2, 6, 7)) 
(0.025, (2, 8, 9)) 
(0.015, (2, 10, 11, 12)) 
(0.020000000000000004, (6, 13, 14)) 
(0.03, (6, 15, 16)) 
>>> 
>>> 
>>> 
>>> for x in prob_tree(mydata3,1): 
    print(x) 


(0.8, (2, 3)) 
(0.004640000000000001, (6, 7, 14, 23, 32)) 
(0.003360000000000001, (6, 7, 14, 42)) 
(0.010800000000000002, (6, 7, 15, 17, 18)) 
(0.0012000000000000001, (6, 7, 15, 20, 21)) 
(0.0116, (8, 9, 14, 23, 32)) 
(0.008400000000000001, (8, 9, 14, 42)) 
(0.027000000000000003, (8, 9, 15, 17, 18)) 
(0.003, (8, 9, 15, 20, 21)) 
(0.006959999999999999, (10, 11, 12, 14, 23, 32)) 
(0.00504, (10, 11, 12, 14, 42)) 
(0.0162, (10, 11, 12, 15, 17, 18)) 
(0.0018, (10, 11, 12, 15, 20, 21)) 
(0.010000000000000002, (2, 6, 7)) 
(0.025, (2, 8, 9)) 
(0.015, (2, 10, 11, 12)) 
(0.0116, (6, 14, 23, 32)) 
(0.008400000000000001, (6, 14, 42)) 
(0.027000000000000003, (6, 15, 17, 18)) 
(0.003, (6, 15, 20, 21)) 
>>> 

EDIT 2 добавления проверки циклических ссылок

def prob_tree_with_check(data,ini,visited=frozenset()): 
    """Generator of all end points of the probability tree contained 
     in data, starting with ini. Check if a previously visited branch 
     of the tree is visited again and raise RuntimeError in that case""" 
    if ini in visited: 
     raise RuntimeError("Branch allready visited: %r"%ini) 
    visited = visited.union((ini,)) 
    for prob,path in data[ini]: 
     no_more,more = map(tuple,partition(lambda x: x in data,path)) 
     if more: 
      for node in itertools.product(*[prob_tree_with_check(data,x,visited) for x in more]): 
       new_prob,new_path = functools.reduce(lambda acum,new: (acum[0]*new[0],acum[1]+new[1]),node,(prob,tuple())) 
       yield new_prob, no_more + new_path 
     else: 
      yield prob, no_more 

mydata_bad = {1: [[.9, [2,3]], [.1, [4,5]]], 
      4: [[.2, [6,7]], [.5, [8,9]], [.3, [10,11,12]]], 
      5: [[.4, [13,14]], [.6, [15,16,1]]] # <-- try to go back to 1 
      } 

выход

>>> for x in prob_tree_with_check(mydata_bad,1): 
    x 


(0.9, (2, 3)) 
Traceback (most recent call last): 
    File "<pyshell#35>", line 1, in <module> 
    for x in prob_tree_with_check(mydata_bad,1): 
    File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 137, in prob_tree_with_check 
    for node in itertools.product(*[prob_tree_with_check(data,x,visited) for x in more]): 
    File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 137, in prob_tree_with_check 
    for node in itertools.product(*[prob_tree_with_check(data,x,visited) for x in more]): 
    File "C:\Users\David\Documents\Python Scripts\stackoverflow_test.py", line 132, in prob_tree_with_check 
    raise RuntimeError("Branch already visited: %r"%ini) 
RuntimeError: Branch already visited: 1 
>>>