Словарь со ссылкой на значение в Python - PullRequest
Новая
       3

Словарь со ссылкой на значение в Python

1 голос
/ 05 января 2020

Есть ли какой-либо метод, доступный в python для получения ключа, которому принадлежит значение, во вложенном словаре?

Примером может быть: 

dic = {1 : 
       {2 : 
        {3 : 4}},
       5 : 
       {6 :
        {7 : 8}}
      }

Где я бы тогда хотел знать путь, по которому нужно идти, чтобы достичь либо 4, либо 8.

Это будет выглядеть примерно так: 

find_path(dic, 8)

, который должен возвращать что-то вроде 

5, 6, 7 # since dic[5][6][7] leads to 8.

Для контекста: Я пытаюсь создать 60^5 В игре указывается ИИ, который я собираюсь реализовать для игры. Мне нужно проанализировать все игровые состояния на глубине 5, чтобы определить, какое лучше. Затем, чтобы достичь состояния на глубине 5, мне нужно знать, какие шаги предпринять на глубине 1, 2, 3 и 4, чтобы достичь этого игрового состояния. Я не знаю, являются ли словари оптимальными для этого, поэтому хотел бы услышать другие предложения, если это возможно.

Ответы [ 4 ]

3 голосов
/ 05 января 2020

Два решения

Первое - рекурсия

Второе - Глубина Первый поиск

Первое решение - Использование рекурсии 

def find_path(d, value, path = [], sol = []):
    for k, v in d.items():
        if isinstance(v, dict):
            path.append(k)
            find_path(v, value, path, sol)
            path.pop()
        elif v == value:
            path.append(k)
            sol.append(path[:])
            path.pop()
    return sol

dic = {1 : {2 : 
             {3 : 4}
            }, 
        5 : {6 :
             {7 : 8}}}

for v in range(10):
    found = find_path(dic, v, [], [])
    if found:
        print("{} -> {}".format(v, found[0))  # showing first solution
                                              # found will show them all
    else:
        print("No path to {}".format(v))

Вывод 

No path to 0
No path to 1
No path to 2
No path to 3
4 -> [1, 2, 3]
No path to 5
No path to 6
No path to 7
8 -> [5, 6, 7]
No path to 9

Второе решение - Использование поиска по глубине 

from collections import deque 

def find_using_dfs(d, value):
    " Finds using depth first searh through dictionary "

    # Use queue for Depth First Search (LIFO)
    stack = deque()

    for k, v in d.items():
        stack.append((v, [k]))

    while stack:
        v, path = stack.pop()
        if isinstance(v, dict):
            for k, viter in v.items():
                path.append(k)
                stack.append((viter, path[:]))
                path.pop()

        elif v == value:
            return path

    return None   

dic = {1 : {2 : 
             {3 : 4}
            }, 
        5 : {6 :
             {7 : 8}}}

for v in range(0, 10):
    found = find_path_proc(dic, v)
    if found:
        print("{} -> {}".format(v, found))
    else:
        print("No path to {}".format(v))

Выход 

No path to 0
No path to 1
No path to 2
No path to 3
4 -> [1, 2, 3]
No path to 5
No path to 6
No path to 7
8 -> [5, 6, 7]
No path to 9
0 голосов
/ 05 января 2020

Еще один способ, которым я могу придумать, - создать перевернутый диктат. Занимает гораздо больше места, но, насколько я могу судить, более эффективен. Это будет выглядеть примерно так: 

dic = {1 :
       {2 :
        {3 : 4}},
       5 :
       {6 :
        {7 : 8}}
      }

inverted_dic = {}

def create_inverted_dic(d):
    def create_inverted_dic_rec(sub_dic,root):
        for k,v in sub_dic.items():
            inverted_dic[k] = root
            if isinstance(v,dict):
                create_inverted_dic_rec(v,k)
            else:
                inverted_dic[v] = k

    for k,v in d.items():
        inverted_dic[k] = None
        create_inverted_dic_rec(v,k)

def find_path(value):
    output = []
    while not value is None:
        value = inverted_dic.get(value,None)
        if value:
            output.append(value)
    output.reverse()
    return output

create_inverted_dic(dic)

for i in range(10):
    print("{} ->  {}".format(i, find_path(i)))

Вывод

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

0 ->  []
1 ->  []
2 ->  [1]
3 ->  [1, 2]
4 ->  [1, 2, 3]
5 ->  []
6 ->  [5]
7 ->  [5, 6]
8 ->  [5, 6, 7]
9 ->  []
0 голосов
/ 05 января 2020

Чтобы сделать это быстро, я бы подумал создать вместо него ключ {key: parent_key}. В вашем случае, 

dic = {1:None, 2:1, 3:2, 4:3, 
       5:None, 6:5, 7:6, 8:7}

Если эти ключи представляют собой сложные игровые состояния, вы можете иметь их в качестве простых идентификаторов и сохранять фактические состояния в отдельном дикте или даже списке. Или вы можете иметь 

class State:
    pass

StateNode = namedtuple('StateNode', ('state', 'parent_id'))
dic = {1: StateNode(State(), None), 2: StateNode(State(), 1), 3: StateNode(State(), 2)}

В любом случае, когда вы знаете идентификатор вашего конечного узла (который, я полагаю, вы знаете), вы можете просто рисовать узлы из dict, пока не достигнете узла с родителем None.

0 голосов
/ 05 января 2020

Вы можете сделать это с помощью networkx: 

from collections import Mapping
import networkx as nx

graph_data = {1 : 
       {2 : 
        {3 : 4}},
       5 : 
       {6 :
        {7 : 8}}
      }
# Empty directed graph
G = nx.DiGraph()

# Iterate through the layers
q = list(graph_data.items())
while q:
    v, d = q.pop()
    for nv, nd in d.items():
        G.add_edge(v, nv)
        if isinstance(nd, Mapping):
            q.append((nv, nd))
        else:
            if not isinstance(nd, dict):
                G.add_edge(nv, nd)

В качестве последнего шага мы можем использовать функцию nx.shortest_path. 

all_paths = nx.shortest_path(G, target=8)
max_len_key =  max(all_paths, key=lambda k: len(all_paths[k]))
print(all_paths[max_len_key])

И на выходе будет: 

[5, 6, 7, 8]
...