сортировка списка питонов на основе «зависимостей» из словаря

Question

Предположим, у меня есть следующий список foo, который я хотел бы отсортировать:

foo = [63,64,65]

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

bar = {
    63: [64, 65],
    64: [65]
}

Например, глядя на список foo, мы видим значение 63 по индексу 0.Но, проверяя словарь bar, мы видим, что 63 имеет "зависимости" 64 и 65, поэтому оба эти значения должны сортироваться выше в foo.

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

ОБНОВЛЕНИЕ: Многие в комментариях указали, что это, вероятно, проблема с графикой / топологией.Спасибо за это, так как на самом деле это часть более крупной задачи сортировки узлов в графе.

Обновление: toposort было предложено посмотреть, и это точно соответствует требованиям.

Answer 1

Итак, собрав все комментарии вместе:

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

В Python уже есть пакет, который может это сделать, toposort.Однако требуется, чтобы ваши значения были наборами, а не списками, но это легко исправить:

from toposort import toposort_flatten

bar = {
    63: [64, 65],
    64: [65]
}

graph = dict(zip(bar.keys(), map(set, bar.values())))
sorted_graph = toposort_flatten(graph, sort=True)

Так как ваш график может содержать записи, которые не находятся в foo, вы можете отсортироватьfoo вот так:

foo = [63,64,65]
foo_set = set(foo)
foo_sorted = [x for x in sorted_graph if x in foo_set]
print(foo_sorted)
# [65, 64, 63]

Или, если график намного больше, чем список, который вы хотите отсортировать (и итерации по нему занимают много времени), создайте словарь:

graph_sorted_lookup = {x: i for i, x in enumerate(sorted_graph)}
foo_sorted = sorted(foo, key=graph_sorted_lookup.get)