Python кода в список зависимостей, избегая петли

Question

Допустим, есть словарь, описывающий зависимости запись, вдоль линий:

deps = { 
    'A': ['B', 'C', 'D'], 
    'B': ['C', 'E'], 
    'C': ['D', 'F'], 
    'D': ['C', 'G'], 
    'E': ['A'], 
    'H': ['N'], 
} 

это означает, что элемент «A» зависит от предметов «B», «C», и «D» и т. Д. Очевидно, это может быть произвольной сложности.

Как вы пишете функцию get_all_deps(item), которая дает вам список всех зависимостей item, без дублей и без item. Например:

> get_all_deps('H') 
['N'] 
> get_all_deps('A') 
['B', 'C', 'D', 'E', 'F', 'G'] 
> get_all_deps('E') 
['A', 'B', 'C', 'D', 'F', 'G'] 

Я ищу сжатый код - в идеале - единственную рекурсивную функцию. Производительность не очень важна для моего случая использования - мы говорим о довольно небольших графиках зависимостей (например, несколько десятков наименований)

Answer 1

вы можете использовать список стека/Todo, чтобы избежать рекурсивного реализации:

deps = { 
    'A': ['B', 'C', 'D'], 
    'B': ['C', 'E'], 
    'C': ['D', 'F'], 
    'D': ['C', 'G'], 
    'E': ['A'], 
    'H': ['N'], 
} 

def get_all_deps(item): 
    todo = set(deps[item]) 
    rval = set() 
    while todo: 
     subitem = todo.pop() 
     if subitem != item: # don't add start item to the list 
      rval.add(subitem) 
      to_add = set(deps.get(subitem,[])) 
      todo.update(to_add.difference(rval)) 
    return sorted(rval) 

print(get_all_deps('A')) 
print(get_all_deps('E')) 
print(get_all_deps('H')) 

результат:

['B', 'C', 'D', 'E', 'F', 'G'] 
['A', 'B', 'C', 'D', 'F', 'G'] 
['N'] 

todo набор содержит элементы, которые будут обработаны.

• Поп один элемент и поставить его в список возвращаемого значения
• Loop, пока не более элементов (хорошо есть петля здесь)
• только добавить элементы для обработки, если они уже не в возвращении стоимость.
• возвращение отсортированный список

Разница set позволяет избежать проблемы с циклическими зависимостями, и «максимальная глубина рекурсии» избежать. Только ограничение - системная память.