порядок ключей Python dict на основе значений - рекурсивное решение - PullRequest
Новая
       19

порядок ключей Python dict на основе значений - рекурсивное решение

0 голосов
/ 20 сентября 2018

(в python 3.6) Как вывести список ключей словаря, в которых порядок списка основан на зависимостях значений словаря?Например, если у меня есть словарь программ, значения которых указывают на другие программы, от которых оно зависит: 

packages = { 'B7': ['R3'], 
             'R3': ['timestmp', 'Abbot', '9K'],
             'tempor': ['cavie', 'sandals', 'B7'],
             'Abbot': ['Duns'],
             'timestmp': [],
             'Duns': [] }

Я бы возвратил список с каждым заказанным элементом на основе программ, необходимых для установки.Поэтому я установил бы timestmp перед R3. 

>>> get_download_order(packages)
['timestmp', 'Duns', 'Abbot', '9K', 'R3', 'B7', 'cavie', 'sandals', 'tempor']

# The list doesn't have to result in this exact order 
# as long as the download order of packages will work.

Для нерекурсивного решения я думал о создании дерева с дочерними элементами и определении родителя, после чего вы могли бы пройти по дереву.Но, видимо, есть рекурсивное решение, и я не могу его понять.

Ответы [ 2 ]

0 голосов
/ 11 мая 2019

Адаптировано из этого ответа : 

from typing import List, Dict, Set

def topological_sort(graph: Dict[str, List[str]]) -> List[str]:
    result: List[str] = []
    seen: Set[str] = set()

    def recursive_helper(node: str) -> None:
        for neighbor in graph.get(node, []):
            if neighbor not in seen:
                seen.add(neighbor)
                recursive_helper(neighbor)
        if node not in result:
            result.append(node)

    for key in graph.keys():
        recursive_helper(key)
    return result


packages = {'B7': ['R3'],
            'R3': ['timestmp', 'Abbot', '9K'],
            'tempor': ['cavie', 'sandals', 'B7'],
            'Abbot': ['Duns'],
            'timestmp': [],
            'Duns': []}

print(topological_sort(packages))

Вывод 

['timestmp', 'Duns', 'Abbot', '9K', 'R3', 'B7', 'cavie', 'sandals', 'tempor']

Это также работает без зависимостей: 

packages = {"B7": [], "R3": []}
print(topological_sort(packages))

Вывод 

['B7', 'R3]
0 голосов
/ 20 сентября 2018

Ваша проблема известна как топологическая сортировка , из Википедии:

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

В вашем конкретном случае вершина графа - это пакеты и ребраявляются зависимостями.Вы можете решить проблему, используя алгоритм Кана (без рекурсии), реализация ниже: 

def toposort(graph):
    # init the indegree for each noe
    nodes = graph.keys() | set([node for adjacents in graph.values() for node in adjacents])
    in_degree = {node: 0 for node in nodes}

    # compute the indegree
    for k, adjacents in graph.items():
        for node in adjacents:
            in_degree[node] += 1

    # init the heap with the nodes with indegree 0 and priority given by key
    heap = [node for node, degree in in_degree.items() if degree == 0]

    top_order = []
    while heap:  # heap is not empty
        node = heap.pop()  # get the element with highest priority and remove from heap
        top_order.append(node)  # add to topological order
        for adjacent in graph.get(node, []):  # iter over the neighbors of the node
            in_degree[adjacent] -= 1
            if in_degree[adjacent] == 0:  # if the node has in_degree 0 add to the heap with priority given by key
                heap.append(adjacent)

    return top_order


packages = {'B7': ['R3'],
            'R3': ['timestmp', 'Abbot', '9K'],
            'tempor': ['cavie', 'sandals', 'B7'],
            'Abbot': ['Duns'],
            'timestmp': [],
            'Duns': []}

reverse = {}
for key, nodes in packages.items():
    for node in nodes:
        reverse.setdefault(node, []).append(key)


print(toposort(reverse))

Вывод 

['timestmp', '9K', 'sandals', 'Duns', 'Abbot', 'R3', 'B7', 'cavie', 'tempor']

Примечание

Для работы предложенного решения необходим перевернутый график, то есть то, что делают следующие строки: 

reverse = {}
for key, nodes in packages.items():
    for node in nodes:
        reverse.setdefault(node, []).append(key)

Также обратите внимание, что порядок не уникален, дляНапример, в вашем примере 'timestmp' и 'Duns' могут быть первыми пакетами для установки, учитывая, что у них нет никаких зависимостей.

Далее

  • Обсуждение алгоритма Канха вместе с реализациями: топологическая сортировка .
  • Рекурсивное решение может быть выполнено с использованием (рекурсивного) поиска в глубину (DFS) для решения топологической сортировки,Вы можете найти хорошее обсуждение рекурсивной DFS здесь .
  • Для использования DFS для решения топологической сортировки см. this .
...