CODEWITHSUNDEEP
rsequence
Jean-François Bourdon
Jean-François Bourdon

Reputation: 142

Reconstruct a sequence from pairs

I am trying to reconstruct sequences from pairs in order to obtain the shortest path (or all paths, I can work with that also) between the element a and all the other elements b, c, d, e. I am working in R. Let say I have these five pairs:

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

The elements of pair can be permuted so bc can become cb. I would like to have at the end these four sequences:

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

I tried with loops and regexpr to find where a specific letter is in all the pairs but I always end up with the problem of how managing multiple combinations. I found this question that is similar to mine (reconstruct a sequence from a set of partial orders) with the answer being to look into topological sorting. I have looked into it but didn't find how exactly I could use this to solve my problem.

Upvotes: 0

Views: 110

Answers (1)

G5W
G5W

Reputation: 37661

You can get the equivalent of this by turning your sequences into graph edges and then using shortest_paths from the igraph package to find the paths

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

You would still need to do a little formatting to get the representation you requested, but this gives the paths that you need.

Upvotes: 2

Related Questions