Python: следовать "пути" кортежей? - PullRequest
Новая
       92

Python: следовать "пути" кортежей?

4 голосов
/ 30 апреля 2020

Короткая версия: Что у меня есть: Список из двух кортежей, например [("a", "b"), ("b", "c"), ("d", "e"), ("c", "d"), ("f", "g")], которые не обязательно упорядочены в алфавитном порядке

Что Я хочу: дать начальную букву (скажем, "a") и конечную букву (скажем, "e"), я бы хотел Python, чтобы найти список доступных 2-кортежей из списка выше, который будет "ссылка "от начальной буквы до последней буквы, поэтому в этом примере этот список будет [("a", "b"), ("b", "c"), ("c", "d"), ("d", "e")] в таком порядке (a --> b --> c --> d --> e)

Более длинная версия: Привет всем, это мой 1-й пост на SO, хотя я просматривал его целую вечность и всегда находил здесь свои ответы, большое сообщество!

У меня есть некоторый анализ данных для моей работы, и у меня есть определенное количество наборов данных (которые Я буду обозначать здесь буквами для простоты), из которых я знаю только математическое различие: ("a" - "b"), ("b" - "c"), et c (это мои входные данные) , Я буду представлять эти входные данные 2-мя кортежами. Идея состоит в том, чтобы вычислить разницу между наборами данных «a» и «e», то есть «a» - «e», которую в этом случае можно получить, суммируя некоторые из разностей промежуточных наборов данных (мои входные данные): (" a "-" b ") + (" b "-" c ") + (" c "-" d ") + (" d "-" e ") =" a "-" e ".

Я бы хотел знать, есть ли модуль Python, который уже делает то, что я хочу, или есть простой способ сделать это, используя синтаксис Python. В приведенном выше простом случае каждая буква появляется только в 2 кортежах из списка, но в общем случае может быть дополнительный кортеж, содержащий правильную букву, но не позволяющий связать начальную букву с конечной буквой (например, если бы был дополнительный кортеж ("b", "h"), он был бы найден на 1-й итерации кода вместе с кортежем ("b", "c"), но его следует отбросить, потому что буква "h" никуда не "ведет"). У меня возникают проблемы с такими делами.

Надеюсь, вопрос достаточно ясен, трудно просто express

Заранее спасибо!

1 Ответ

5 голосов
/ 30 апреля 2020

Похоже, что путь к go здесь - использовать некоторый инструмент анализа графа, чтобы найти кратчайший путь между парой узлов. Хотя этот случай на самом деле несколько упрощает проблему, поскольку вы упоминаете, что каждая буква появляется только в 2 кортежах из списка , что означает, что будет только один путь, соединяющий пару узлов. Хотя общий сценарий состоит в том, чтобы иметь несколько возможных путей, соединяющих исходный и целевой узлы, в этом случае нам нужен какой-то алгоритм, чтобы найти самый короткий из них.

Так что способ go об этом - использовать NetworkX для построения графа, в котором список кортежей представляет ребра графа и ищет nx.shortest_path между парой source и target узлов: 

import networkx as nx

edges = [("a", "b"), ("b", "c"), ("d", "e"), ("c", "d"), ("f", "g")]

G = nx.from_edgelist(edges)
path_nodes = nx.shortest_path(G, 'a', 'e')
# ['a', 'b', 'c', 'd', 'e']

Если вы хотите получить вывод в виде списка кортежей, вы можете легко сделать: просто в основном определяет граф из предоставленных ребер, а shortest_path будет просто искать минимально необходимые ребра графа для соединения исходного и целевого узлов.

...