没有任何进口
# given
deps = {'W': ['R', 'S'], 'C': [], 'S': ['C'], 'R': ['C'], 'F': ['W']}
prob = {'C': [0.5], 'R': [0.2, 0.8], 'S': [0.5, 0.1], 'W': [0.01, 0.9, 0.9, 0.99], 'F' : [0.4, 0.3]}
k = 'F'
# want to return: L = [[0.2, 0.8], [0.5, 0.1], [0.01, 0.9, 0.9, 0.99], [0.4, 0.3]]
# attempt
L = []
for i in deps[k]:
s = i
while(deps[s] != []):
L.append(prob[s])
s = deps[s]
print(L)
我很难搞清楚这一点。所以给出了两个词典:依赖和概率我希望遍历一个选择点并设置每个值,所以对于上面的例子,我选择了'F'。
首先进入'F'的代表,找到'W',然后检查那些是''R','S'的deps然后检查'R',看看'R'的依赖是'C'并且'C'不是一个依赖者,所以我们停在'R'并将其概率附加到L.
[[0.2, 0.8]]
然后我们进入S并做同样的事情
[[0.2, 0.8], [0.5, 0.1]]
然后我们就完成了,我们回到了W
[[0.2, 0.8], [0.5, 0.1], [0.01, 0.9, 0.9, 0.99]]
最后,由于我们已经完成了W,我们得到了F的概率词
[[0.2, 0.8], [0.5, 0.1], [0.01, 0.9, 0.9, 0.99], [0.4, 0.3]]
当有多个依赖值时,我的代码会失败。不知道如何包围我的头。尝试使用deps和k的概率和值来创建一个能够执行此操作的函数
这是一个使用基于堆栈的深度优先搜索来遍历依赖关系树的解决方案。它增加了每一步iff的概率。节点具有依赖关系,然后在最后简单地反转列表。
def prob_list(root):
nodes_to_visit = [root]
prob_list = []
while nodes_to_visit:
curr = nodes_to_visit.pop()
print(f"Visiting {curr}")
if deps[curr]:
prob_list.append(prob[curr])
for dep in deps[curr]:
nodes_to_visit.append(dep)
return list(reversed(prob_list))
print(prob_list("F")) # [[0.2, 0.8], [0.5, 0.1], [0.01, 0.9, 0.9, 0.99], [0.4, 0.3]]
我会用while
循环来解决这个问题,这个循环一直在查看你是否已经使用了你递归找到的所有值。您可以使用以下结构:
deps = {'W': ['R', 'S'], 'C': [], 'S': ['C'], 'R': ['C'], 'F': ['W']}
# out = ['F', 'W', 'R', 'S']
prob = {'C': [0.5], 'R': [0.2, 0.8], 'S': [0.5, 0.1], 'W': [0.01, 0.9, 0.9, 0.99], 'F': [0.4, 0.3]}
k = 'F'
L = []
my_list = []
found_all = False
def get_values(dep_dictionary, prob_dict, start_key):
used_keys = []
keys_to_use = [start_key]
probability = []
# build a list of linked values from deps dictionary
while used_keys != keys_to_use:
print('used: {}'.format(used_keys))
print('to use: {}'.format(keys_to_use))
for i in range(len(keys_to_use)):
if keys_to_use[i] not in used_keys:
new_keys = dep_dictionary[keys_to_use[i]]
if len(new_keys):
for sub_key in new_keys:
if sub_key not in keys_to_use:
keys_to_use.append(sub_key)
used_keys.append(keys_to_use[i])
else:
del keys_to_use[i]
# at this point used_keys = ['F', 'W', 'R', 'S']
for key in used_keys:
probability.append(prob_dict[key])
print(probability)
get_values(deps, prob, k)
哪个输出:
used: []
to use: ['F']
used: ['F']
to use: ['F', 'W']
used: ['F', 'W']
to use: ['F', 'W', 'R', 'S']
used: ['F', 'W', 'R', 'S']
to use: ['F', 'W', 'R', 'S', 'C']
[[0.4, 0.3], [0.01, 0.9, 0.9, 0.99], [0.2, 0.8], [0.5, 0.1]]
你可以看到输出是正确的([[0.4, 0.3], [0.01, 0.9, 0.9, 0.99], [0.2, 0.8], [0.5, 0.1]]
),但它的顺序并不完全相同,但听起来不应该是一个巨大的问题。如果是,您可以通过调整将其重新拼接成字典
for key in used_keys:
probability.append(prob_dict[key])
有点像probability
也是字典。你也可以把print()
语句拿出来,它们只是在那里进行调试并直观地显示循环中发生了什么。您也可能有return probability
功能而不是打印它,但我会自行决定!