Восстановить последовательность из пар

Question

Я пытаюсь восстановить последовательности из пар, чтобы получить кратчайший путь (или все пути, я могу работать с этим также) между элементом a и все остальные элементы b, c, d, e, Я работаю в R. Допустим, у меня есть эти пять пар:

c("ae","bc","cd","ca","de")

Элементы пары могут быть переставлены так bc может стать cb, Я хотел бы иметь в конце эти четыре последовательности:

c("ae") #from  a to e
c("ac") #from  a to c
c("ae","ed") #from  a to d
c("ac","cb") #from  a to b

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

Answer 1

Вы можете получить эквивалент этого, превратив свои последовательности в ребра графа, а затем используя shortest_paths из пакета igraph, чтобы найти пути

library(igraph)
x = c("ae","bc","cd","ca","de")
EdgeList = matrix(unlist(strsplit(x, "")), ncol=2, byrow=TRUE)
g = graph_from_edgelist(EdgeList , directed = FALSE)
shortest_paths(g, "a")$vpath

[[1]]
+ 1/5 vertex, named:
[1] a

[[2]]
+ 2/5 vertices, named:
[1] a e

[[3]]
+ 3/5 vertices, named:
[1] a c b

[[4]]
+ 2/5 vertices, named:
[1] a c

[[5]]
+ 3/5 vertices, named:
[1] a e d

Вам все равно придется немного отформатировать, чтобы получить запрошенное представление, но это дает необходимые вам пути.