蟒蛇分解字典

Question

我有一个字典，比如

start = 50
end = 84
data = {
'50-52': 781445.0, 
'52-84': 56554260.0, 
'50-73': 31204670.0, 
'73-84': 39169560.0,
'73-75' : 23123123.0,
'75-84' : 2312322.0
}

我想要实现什么？

我想从头到尾遍历所有可能的路径，例如：对于上面的例子

>  x = data['50-52'] + data['52-84'] = 781445.0 + 56554260.0
>  y = data['50-73'] + data['73-84'] = 31204670.0 + 39169560.0
>  z = data['50-73'] + data['73-75'] + data['75-84'] = 31204670.0 + 23123123.0 + 2312322.0

我想从头到尾了解所有可能的路径list，这是[x, y, z]

我一直在尝试解决这个问题的不同方式已经陷入了死胡同。我尝试创建新的字典并在每次迭代时更新它，但代码似乎变得非常复杂，关于我可以采取什么方法的任何想法？

谢谢！

Answer 1

这种类型的信息最好用图表来表示：

import networkx as nx

data = {
'50-52': 781445.0, 
'52-84': 56554260.0, 
'50-73': 31204670.0, 
'73-84': 39169560.0,
'73-75' : 23123123.0,
'75-84' : 2312322.0
}
G = nx.DiGraph()
for key, weight in data.items():
src_str, dest_str = key.split('-')
src_idx, dest_idx = int(src_str), int(dest_str)
G.add_edge(src_idx, dest_idx, weight=weight)
start = 50
end = 84
all_paths = list(nx.all_simple_paths(G, 
source=start, 
target=end))
distances = [sum(G.get_edge_data(s,d)['weight'] for s,d in zip(p,p[1:])) 
for p in all_paths]

results = {tuple(p):d for p,d in zip(all_paths,distances)}

print(results)

结果是：

{
(50, 52, 84): 57335705.0, 
(50, 73, 84): 70374230.0, 
(50, 73, 75, 84): 56640115.0
}

Networkx可能有点棘手，但绝对值得学习！

Answer 2

你也可以用combinations暴力破解它。 我不确定您的dict有多大，但如果您只需要计算一两次，这里有一个解决方案。

from itertools import combinations
def get_paths(start, end, all_paths):
paths = []
# this will produce a list of tuples of all the coordinates
# convert to ints for sorting purposes
cooards = [(int(i.split('-')[0]), int(i.split('-')[1])) for i in all_paths]
# this produces a list of all possible combinations
# of those coordinates
# basically a list of all possible lengths
# of all possible combinations for each length
combs = [x for l in range(1, len(cooards) + 1) for x in combinations(cooards, l)]
for path in combs:
# sort the path so we can traverse it in order to see if 
# the end element matches the start of the next element
full_path = sorted(path)
path_start = full_path[0][0]
path_end = full_path[-1][1]
# invlidate anything without a proper start and end point
if start == path_start and end == path_end:
# paths with a length of 1 immediately qualify
if len(full_path) == 1:
paths.append(['-'.join(str(j) for j in i) for i in path])
else:
# if we get through our entire path without breaking we qualify
for i, cooard in enumerate(full_path[:-1]):
if cooard[1] != full_path[i + 1][0]:
break
else:
# convert back to strings so we can use the keys
paths.append(['-'.join(str(j) for j in i) for i in path])
return paths

start = 50
end = 84
data = {
'50-52': 781445.0, 
'52-84': 56554260.0, 
'50-73': 31204670.0, 
'73-84': 39169560.0,
'73-75' : 23123123.0,
'75-84' : 2312322.0
}
print(get_paths(start, end, data))

从这里很容易获得返回的键的总和。