Python разложение дикта

Question

У меня есть такой dict, как

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]

Я как бы зашел в тупик с различные способы, которыми я пытался подойти к этому. Я пытался создать новый dict и обновлять его с каждой итерацией, но код кажется очень сложным, есть идеи, какой подход я могу использовать?

Спасибо!

Answer 1

Вы также можете перебрать его с помощью 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))

Отсюда было бы легко получить сумму возвращенных ключи.

Answer 2

Этот тип информации лучше всего представить с помощью графиков:

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 может быть немного сложным, но о нем определенно стоит узнать!