Словарь зацикливание, получая каждое значение - PullRequest
Новая
       22

Словарь зацикливание, получая каждое значение

2 голосов
/ 03 апреля 2019

без каких-либо импортов 

# 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 словаря: зависимости и вероятность, я хочу пройти через точку выбора и установить каждое значение, поэтому для приведенного выше примера я выбрал «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

Ответы [ 2 ]

1 голос
/ 03 апреля 2019

Я бы решил проблему с помощью цикла 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 вместо ее печати, но я оставлю это на ваше усмотрение!

0 голосов
/ 03 апреля 2019

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

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