字典循环获取每个值

Question

没有任何进口

# 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)

我无法弄清楚这一点。因此，给定 2 个字典：依赖项和概率，我希望遍历 select 点并设置每个值，因此对于上面的示例，我选择了 'F'。

它将首先进入 'F' 的部门，找到 'W'，然后检查 ['R'、'S'] 的部门，然后检查 '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 和 prob 以及 k

的值的情况下执行此操作

Answer 1

我会用一个 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])

bit 这样 probability 也是一个字典。您还可以取出 print() 语句，它们只是用来调试和直观地显示循环中发生的事情。您也可能会使用函数 return probability 而不是打印它，但我将由您自行决定！

Answer 2

这是一个使用基于堆栈的深度优先搜索来遍历依赖树的解决方案。它增加了每一步的概率。该节点有依赖关系，然后在最后简单地反转列表。

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]]

字典循环获取每个值

Dictionary looping getting every value

python

dictionary

traversal