Сортировка словарей в python по значениям, которые на самом деле являются списками

Question

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

{"A": [["B", 10], ["D", 5]], "B": [["A", 10], ["C", 5]], "C ": [[" B ", 5], [" D ", 15]]," D ": [[" C ", 15], [" A ", 5]]}.

Также мне разрешено импортировать только библиотеку копирования, поэтому я могу скопировать один список и использовать deepcopy () для создания нового объекта с теми же элементами.

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

def edge_get(graph):

    input_list = []
    sorted_list = []

    for key, value in graph.items():
        temp = [key,value]
        input_list.append(temp)

    print(input_list)

Это распечатывает ...

[['A', [['B', 10], ['D', 5]]], ['B', [['A', 10], ['C', 5]] ], ['C', [['B', 5], ['D', 15]]], ['D', [['C', 15], ['A', 5]]]]

Я бы хотел получить его на выходе:

[['A', 'B', 10], ['A', 'D', 5], ['B', 'A', 10], ['B', 'C', 5 ], ...

Я полагаю, что если я смогу получить это так, я могу сравнить третий элемент каждого списка в списке, и если они одинаковы, проверить, совпадают ли другие элементы (тот же край). И на основании этого я могу добавить его в окончательный список или забыть и двигаться дальше.

Для этого примера конечная цель:

[['A', 'D'], ['B', 'C'], ['A', 'B'], ['C', 'D']]

Answer 1

Итак, у вас есть диктат, представляющий граф в виде списка смежности, и вы хотите преобразовать этот список смежности в список ребер.

Это можно сделать с помощью понимания вложенного списка:

graph = {"A": [["B",10], ["D",5]], "B": [["A",10], ["C",5]], "C": [["B",5],["D",15]], "D": [["C",15], ["A",5]]}
edges = [(src, dst, weight) for src, adjs in graph.items() for dst, weight in adjs]
# edges = [('A', 'B', 10), ('A', 'D', 5), ('B', 'A', 10), ('B', 'C', 5), ('C', 'B', 5), ('C', 'D', 15), ('D', 'C', 15), ('D', 'A', 5)]

Затем вы можете устранить дубликаты ребер, преобразовав их в диктовку. Обратите внимание, что если у вас есть дубликаты ребер с конфликтующими весами, это выберет один из весов произвольно:

uniques = {frozenset([src, dst]): weight for src, dst, weight in edges}
# uniques = {frozenset({'B', 'A'}): 10, frozenset({'A', 'D'}): 5, frozenset({'B', 'C'}): 5, frozenset({'C', 'D'}): 15}

, а затем отсортирует ребрас сортировкой:

sorted_uniques = sorted(uniques.items(), key=lambda v: v[1])
# sorted_uniques = [(frozenset({'A', 'D'}), 5), (frozenset({'C', 'B'}), 5), (frozenset({'A', 'B'}), 10), (frozenset({'C', 'D'}), 15)]

Наконец, чтобы получить результат в структуре, которую вы хотели, вы просто делаете:

result = [sorted(e) for e, weight in sorted_uniques]
# result = [['A', 'D'], ['B', 'C'], ['A', 'B'], ['C', 'D']]

Answer 2

Вы можете представить каждое ребро как frozenset и отфильтровать дубликаты ребер с помощью set:

G = {"A": [["B",10], ["D",5]], "B": [["A",10], ["C",5]], "C": [["B",5],["D",15]], "D": [["C",15], ["A",5]]}

edges = {(frozenset((k, i)), j) for k, v in G.items()
                                for i, j in v}
[sorted(i) for i, _ in sorted(edges, key=lambda x: x[1])]
# [['B', 'C'], ['A', 'D'], ['A', 'B'], ['C', 'D']]

Answer 3

Вы можете использовать itertools.product для генерации комбинаций клавиш с каждым связанным подсписком.Если вы отсортируете и распакуете строковые компоненты каждой комбинации, то вы получите начальный вывод, который вы ищете.Оттуда вы можете отсортировать весь список сначала по значению веса, а затем по вершинам, чтобы получить упорядоченный список.Если вы нарежете этот список значением шага, вы можете удалить дубликаты.Затем вы можете просто удалить значение веса, чтобы получить список пар для вашего окончательного результата.

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

from itertools import product
from operator import itemgetter

d = {"A": [["B",10], ["D",5]], "B": [["A",10], ["C",5]], "C": [["B",5],["D",15]], "D": [["C",15], ["A",5]]}

combos = [[*sorted([c1, c2]), n] for k, v in d.items() for c1, [c2, n] in product(k, v)]
print(combos)
# [['A', 'B', 10], ['A', 'D', 5], ['A', 'B', 10], ['B', 'C', 5], ['B', 'C', 5], ['C', 'D', 15], ['C', 'D', 15], ['A', 'D', 5]]

ordered = sorted(combos, key=itemgetter(2, 0, 1))[::2]
print(ordered)
# [['A', 'D', 5], ['B', 'C', 5], ['A', 'B', 10], ['C', 'D', 15]]

pairs = [o[:-1] for o in ordered]
print(pairs)
# [['A', 'D'], ['B', 'C'], ['A', 'B'], ['C', 'D']]

РЕДАКТИРОВАТЬ (без импорта):

Для комментария подчеркивается ограничение на использование импорта в вашем решении, вот измененная версия оригинала.Различия заключаются в замене itertools.product пониманием списка, которое выполняет то же самое, и замене operator.itemgetter на лямбду.

d = {"A": [["B",10], ["D",5]], "B": [["A",10], ["C",5]], "C": [["B",5],["D",15]], "D": [["C",15], ["A",5]]}

combos = [[*sorted([k, c]), n] for k, v in d.items() for c, n in v]
print(combos)
# [['A', 'B', 10], ['A', 'D', 5], ['A', 'B', 10], ['B', 'C', 5], ['B', 'C', 5], ['C', 'D', 15], ['C', 'D', 15], ['A', 'D', 5]]

ordered = sorted(combos, key=lambda x: (x[2], x[0], x[1]))[::2]
print(ordered)
# [['A', 'D', 5], ['B', 'C', 5], ['A', 'B', 10], ['C', 'D', 15]]

pairs = [o[:-1] for o in ordered]
print(pairs)
# [['A', 'D'], ['B', 'C'], ['A', 'B'], ['C', 'D']]