用Python按实际为列表的值对字典进行排序。

Question

如果我得到一个字典来表示图，其中顶点是键，值是列表，其条目包含相邻顶点和两个顶点之间的权重，我该如何返回按增量排序且没有重复的边缘列表？例如，我可能会得到以下字典：{"A": [["B",10], ["D",5]], "B": [["A",10], ["C",5]], "C": [["B",5],["D",15]], "D": [["C",15], ["A",5]]}。此外，我只被允许导入copy库，因此我可以复制一个列表并使用deepcopy（）创建具有相同元素的新对象。现在，我正在尝试将字典转换为列表，因为我认为在列表内部对元素进行排序并删除重复的边缘可能更容易。所以，目前我有以下内容（graph是字典，在这种情况下提供了上述内容）...

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']]

- IsaacJ700

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对边进行排序：

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']]

- Lie Ryan

Answer 2

您可以使用 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，实现了相同的功能，并用lambda替换了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']]

- benvc

---

OP不允许使用“import”命令。 - Mykola Zotko

Answer 3

你可以使用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']]

- Mykola Zotko