Python -> список сортировки на основе зависимостей между элементами - PullRequest
Новая
       17

Python -> список сортировки на основе зависимостей между элементами

0 голосов
/ 06 июня 2019

У меня есть список значений следующим образом: 

[1,2,3,4,5,6,7,8,9]

Далее у меня также есть диктат зависимостей следующего формата: 

{1 : [2,3], 3: [4], 6: [7,8,9]}

Это означает, что 2,3должны появиться в списке до 1, 4 должны появиться в списке до 3, а 7, 8, 9 должны появиться в списке до 6.

Следовательно, допустимой сортировкой будет: 

[4,2,3,1,7,8,9,6]

На основе этого примера я написал код, который может разбить список на три подмножества:

  1. элементы, которые появляются только наRHS (все они должны быть в верхней части списка) -> 7, 8, 9, 4, 2
  2. элементы, которые появляются только на LHS (их можно разместитьвнизу списка) -> 1, 6
  3. Элементы, которые отображаются как на RHS, так и на LHS -> 3

Я борюсь снаписание кода для сортировки предметов, которые попадают в третью категорию:

Что было бы хорошим способом сортировки этих предметов?

РЕДАКТИРОВАТЬ: 

supersetR = set({})
supersetL = set({})
for dependency in dependencies: 
    supersetR = supersetR.union(dependencies[dependency])
    supersetL.add(dependency)

onlyL = supersetL - supersetR
onlyR = supersetR - supersetL 
LandR = supersetL.intersection(supersetR)

Ответы [ 4 ]

2 голосов
/ 06 июня 2019

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

import networkx
dict_sort = {1 : [2,3], 3: [4], 6: [7,8,9]}

graph = networkx.DiGraph(dict_sort)
list(reversed(list(networkx.topological_sort(graph))))

Выход: 

[2, 4, 3, 1, 7, 8, 9, 6]
2 голосов
/ 06 июня 2019

Ваш диктант на самом деле является ориентированным графом.То, что вы хотите получить, называется топологическая сортировка .В Python есть замечательная библиотека для обработки графиков - networkx , в которой ваша проблема может быть решена с помощью пары строк: 

G = nx.DiGraph({1 : [2,3], 3: [4], 6: [7,8,9]})
list(reversed(list(nx.topological_sort(G))))

[2, 4, 3, 1, 8, 9, 7, 6]

PS Обратите внимание, что ваша проблема может быть решена только в случаях DAG, без каких-либо циклов.Вы не можете упорядочить свой список должным образом в случае этого.Представьте себе график 1->2->3->1.Что бы вы ни записали в список: 

[1,2,3]
[2,3,1]
[3,1,2]

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

nx.is_directed_acyclic_graph(G)

0 голосов
/ 06 июня 2019

Это сортировка? Или просто ходить по графику? 

tree = {1 : [2,3], 3: [4], 6: [7,8,9]}

# basic depth-first search of a graph
def dfs(tree, value, depth=0):
    if value in tree:
        for v in tree[value]:
            dfs(tree, v, depth+1)
    print(value, end=' ')

# find roots - nodes not listed as subs of any other node
roots = [v for v in tree if not any(v in vv for vv in tree.values())]

for r in roots:
    dfs(tree, r)

Дает: 

2 4 3 1 7 8 9 6

Что, кажется, удовлетворяет всем вашим ограничениям.

0 голосов
/ 06 июня 2019

Этот пример кода Розетты топологической сортировки обрабатывает случай, когда зависимости могут давать несколько подходящих упорядочений, показывая элементы, чьи подопорядки все еще соответствуют зависимостям.
Например: если 2 и 3должен появляться перед 1, а элементы равны 1, 2, 3, and 4, тогда порядок 2 относительно 3 и 4 относительно 1, 2 и 3 является переменным.

Код также обнаруживает циклы и имеет примеры выполнения,

...