如何根据字典键的列表值匹配条件对其进行分组？

Question

如何根据字典键的列表值匹配条件对其进行分组？

pythonpython-3.xlistdictionarycollections

3

我希望能够根据分配给键的列表值来对字典的键进行分组。例如，

edge_dict = {'ED7':[[15,-10,0], [20,-10,0]], 'ED10':[[0,0,0],[10,0,0]], 'ED13':[[15,0,0], [20,0,0]], 'ED4':[[20,0,0], [25,0,0]], 'ED2':[[15,0,0], [10,0,0]], 'ED5':[[0,-10,0],[10,-10,0]], 'ED6':[[15,-10,0], [10,-10,0]], 'ED8':[[20,-10,0], [25,-10,0]]}

rib1_edges  :  ['ED10', 'ED5']

rib2_edges  :  ['ED4', 'ED8']

字典“edge_dict”中有一个键'ED10'，其子列表([10,0,0])与同一字典中的另一个键相等，即'ED2'。同样地，我想收集并分组所有那些由共同子列表值连接的键。

预期答案为

selected_group_1 = {'ED10':[[0,0,0],[10,0,0]], 'ED2':[[15,0,0], [10,0,0]], 'ED13':[[15,0,0], [20,0,0]], 'ED4':[[20,0,0], [25,0,0]]}
selected_group_2 = {'ED5':[[0,-10,0],[10,-10,0]], 'ED6':[[15,-10,0], [10,-10,0]], 'ED7':[[15,-10,0], [20,-10,0]], 'ED8':[[20,-10,0], [25,-10,0]]}

需要注意的是，所选组从列表rib1_edges到rib2_edges的值具有顺序。这意味着一个组以键“ED10”开始，并且根据edge_dict中的值如何排列，以“ED4”或“ED8”结尾。

有谁能帮我按预期答案将字典“edge_dict”分组吗？

我开始尝试了一些代码，如下：

import math

def is_equal(pnt1, pnt2):
    L = math.sqrt((pnt1[0]-pnt2[0]) ** 2 + (pnt1[1]-pnt2[1]) ** 2 + (pnt1[2]-pnt2[2]) ** 2)
    if L<1e-4:
        return True
    else:
        return False

for i in range(len(list(edge_dict.keys()))/2):
    for ed, pnts in {k:v for k, v in edge_dict.items() if k not in list(selected_group_1.keys())}.items():
        if (any(is_equal(selected_group_1[edge][0], pnts[0]) or any(is_equal(selected_group_1[edge][1], pnts[0]) or any(is_equal(selected_group_1[edge][0], pnts[1]) or any(is_equal(selected_group_1[edge][1], pnts[1])):
            selected_group_1[ed] = pnts

我无法正确地编写逻辑。需要帮助，感激不尽。

- Paul Thomas

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ruan · Accepted Answer

您需要的是一个可以计算图中连通组件的算法。虽然您可以使用DFS或BFS手动编写它，但有时使用现成的解决方案（例如scipy.sparse.csgraph.connected_components）更方便。

您必须以一种算法可以处理的方式转换您的图。

键和值反转

反转键和值并构建字典dct。

from collections import defaultdict
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

edge_dict = {
    'ED7':[[15,-10,0], [20,-10,0]],
    'ED10':[[0,0,0],[10,0,0]],
    'ED13':[[15,0,0], [20,0,0]],
    'ED4':[[20,0,0], [25,0,0]],
    'ED2':[[15,0,0], [10,0,0]],
    'ED5':[[0,-10,0],[10,-10,0]],
    'ED6':[[15,-10,0], [10,-10,0]],
    'ED8':[[20,-10,0], [25,-10,0]]
}

edge_pairs = [ ['ED10', 'ED5'], ['ED4', 'ED8'] ]

dct = defaultdict(list)

for item in edge_dict.items():
    key = item[0]
    value = item[1]
    for lst in value:
        hashed_lst = str(lst)
        dct[hashed_lst].append(key)

print(dct)

这将是dct的输出结果。

# defaultdict(<class 'list'>, {'[15, -10, 0]': ['ED7', 'ED6'],
# '[20, -10, 0]': ['ED7', 'ED8'],
# '[0, 0, 0]': ['ED10'],
# '[10, 0, 0]': ['ED10', 'ED2'],
# '[15, 0, 0]': ['ED13', 'ED2'],
# '[20, 0, 0]': ['ED13', 'ED4'],
# '[25, 0, 0]': ['ED4'],
# '[0, -10, 0]': ['ED5'],
# '[10, -10, 0]': ['ED5', 'ED6'],
# '[25, -10, 0]': ['ED8']})

邻接表

构建一个ED标签的邻接表，并将其命名为graph_dct。如果两个标签之间存在一条边，则它们属于同一组。

graph_dct = defaultdict(list)

for lst in dct.values(): for item in lst: for item2 in lst: if item != item2: graph_dct[item].append(item2)

print(graph_dct)

以下是graph_dct的输出结果。

    # graph_dct :
    # defaultdict(<class 'list'>, {'ED7': ['ED6', 'ED8'],
    # 'ED6': ['ED7', 'ED5'],
    # 'ED8': ['ED7'], 'ED10': ['ED2'],
    # 'ED2': ['ED10', 'ED13']
    # 'ED13': ['ED2', 'ED4'],
    # 'ED4': ['ED13'], 'ED5': ['ED6']})

邻接矩阵

这是scipy连通组件算法的要求。我们必须将邻接表转换为邻接矩阵。它将被称为sparse_matrix。

graph_dct_keys = list(graph_dct.keys());

sparse_matrix = []
for key in graph_dct_keys:
    row = [0] * len(graph_dct_keys)
    for item in graph_dct[key]:
        row[graph_dct_keys.index(item)] = 1
    sparse_matrix.append(row)

算法

现在我们将sparse_matrix传递给连通组件算法，然后它会给你分组。

components = csr_matrix(sparse_matrix)
n_components, labels = connected_components(csgraph=components, directed=False, return_labels=True)

labels_dct = defaultdict(list)

for idx, item in enumerate(labels):
    labels_dct[str(item)].append(graph_dct_keys[idx])

print(labels_dct.values())
# dict_values([
# ['ED7', 'ED6', 'ED8', 'ED5'],
# ['ED10', 'ED2', 'ED13', 'ED4']
# ])

results = list(labels_dct.values())

现在你有了一个名为results的列表，其中包含可以轻松构建您期望答案的标签列表。

排序

接下来，我们将根据要求对results进行排序，并生成期望的答案。

results = [['ED7', 'ED6', 'ED8', 'ED5'], ['ED10', 'ED2', 'ED13', 'ED4']]
rib1_edges = ['ED10', 'ED5']
rib2_edges = ['ED4', 'ED8']
for idx,lst in enumerate(results):
    results[idx] = sorted(lst, key=lambda x: int(x.lstrip('ED')) )
for idx,lst in enumerate(results):
    results[idx] = [ x for x in rib1_edges if x in lst ] + \
        [ x for x in lst if x not in rib1_edges and x not in rib2_edges ] + \
        [ x for x in rib2_edges if x in lst ]

print(results)

这将给出所需的结果，[['ED5'，'ED6'，'ED7'，'ED8']，['ED10'，'ED2'，'ED13'，'ED4']]。

获取答案

请注意，如果您使用Python 3.6以下版本，则无法保证此字典将按顺序插入。在这种情况下，键可能以任何Python内部算法确定的表面上随机的顺序出现。

因此，如果您正在运行Python 3.6+，可以使用字典，但为了可移植性，最好使用OrderedDict。

from collections import OrderedDict

edge_dict = {
    'ED7':[[15,-10,0], [20,-10,0]],
    'ED10':[[0,0,0],[10,0,0]],
    'ED13':[[15,0,0], [20,0,0]],
    'ED4':[[20,0,0], [25,0,0]],
    'ED2':[[15,0,0], [10,0,0]],
    'ED5':[[0,-10,0],[10,-10,0]],
    'ED6':[[15,-10,0], [10,-10,0]],
    'ED8':[[20,-10,0], [25,-10,0]]
}

result = [
          ['ED5', 'ED6', 'ED7', 'ED8'],
          ['ED10', 'ED2', 'ED13', 'ED4']
]

answer = []
for lst in result:
    od = OrderedDict()
    for item in lst:
        od[item] = edge_dict[item]
    answer.append(od)

import pprint
pp = pprint.PrettyPrinter()
pp.pprint(answer)

然后这将给我们期望的答案。

[OrderedDict([('ED5', [[0, -10, 0], [10, -10, 0]]),
              ('ED6', [[15, -10, 0], [10, -10, 0]]),
              ('ED7', [[15, -10, 0], [20, -10, 0]]),
              ('ED8', [[20, -10, 0], [25, -10, 0]])]),
 OrderedDict([('ED10', [[0, 0, 0], [10, 0, 0]]),
              ('ED2', [[15, 0, 0], [10, 0, 0]]),
              ('ED13', [[15, 0, 0], [20, 0, 0]]),
              ('ED4', [[20, 0, 0], [25, 0, 0]])])]