Получения всех комбинаций рекурсивны [Python]

Question

Рассмотрим словаря:

{ "A": [ ["B"], ["C"] ], 
    "B": [ ["D"], ["E"] ], 
    "C": [ ["H"] ], 
    "D":[["I"],["J"]] 
} 

Я хочу, чтобы найти все возможные пути, которые ведут к А, не в ключах словаря. Например

A = [ [B], [C] ] 

мы можем расширить, что

A = [ [B, D, I],[B, D, J], [B, E], [C, H] ] 

Я пытаюсь придумать рекурсивного решение, но я не могу получить что-нибудь, чтобы полностью работать. Любые предложения по подходу к этой проблеме?

Answer 1

Вы можете найти весь путь со следующей функцией, но поскольку вы не публикуете свой код, и я не знаю, что вы пытаетесь сделать самим собой, поэтому я не знаю, где у вас проблемы, и я не мог объяснить ничего, пока вы не рассказать о своей попытке, и этот код:

def find_all_paths(graph, start,path=[]): 
     path=path+[start] 
     if not graph.has_key(start): 
      return [path] 
     paths = [] 
     for nodes in graph[start]: 
      for n in nodes : 
      if n[0] not in path: 
        newpaths = find_all_paths(graph, n[0], path) 
        for newpath in newpaths: 
         paths.append(newpath) 
     return paths 

g={ "A": [ ["B"], ["C"] ], 
    "B": [ ["D"], ["E"] ], 
    "C": [ ["H"] ], 
    "D":[["I"],["J"]] 
} 

Demmo:

print find_all_paths(g,'A') 
[['A', 'B', 'D', 'I'], ['A', 'B', 'D', 'J'], ['A', 'B', 'E'], ['A', 'C', 'H']] 

print find_all_paths(g,'B') 
[['B', 'D', 'I'], ['B', 'D', 'J'], ['B', 'E']]