我想根据分配给键的列表值对字典的键进行分组。例如,
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”。同样,我想收集并分组 edge_dict 中由公共(public)子列表值连接的所有键。
预期的答案是
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”开始,以“ED4”或“ED8”结束,具体取决于值在 edge_dict 中的排列方式。
谁能帮我按照预期答案对字典“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
我无法正确表达逻辑。任何帮助将不胜感激。
最佳答案
您基本上是在寻求一种可以计算图中连通分量的算法。尽管您可以使用 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']})
邻接表
构建一个 adjacency list您的 ED 标签并将其命名为
graph_dct
。如果两个标签之间有边,则它们属于同一组。graph_dct = defaultdict(列表)
对于 dct.values() 中的 lst: 对于 lst 中的项目: 对于 lst 中的 item2: 如果项目 != 项目 2: 图_dct[item].append(item2)
打印(图形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 连通分量算法的要求。我们必须将邻接表转换为 adjacency matrix。 .它将被称为 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 = [['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']]
.
得到答案
请注意,如果您使用低于 3.6 的 Python 版本,则无法保证该词典将按插入顺序排列。在那种情况下,键可能以任何看似随机的顺序出现,由 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]])])]
关于python - 如何根据列表值匹配条件对字典键进行分组?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54729579/