r - 从头到尾生成顺序配对值的不同长度向量

Question

抱歉，如果这个问题之前已经被问过 - 我正在努力思考如何措辞我的搜索(因此标题很尴尬)！

我有一个单字符值的数据框，如下所示：

-------------------------
|  Parent  |  Daughter  |
-------------------------
|     A    |     B      |
|     B    |     C      |
|     B    |     D      |
|     A    |     E      |
-------------------------

每个父母总有两个女儿(就像一个完整的二叉树)。我正在尝试编写一段代码，该代码将生成从顶部父级到最终子级的路径向量：

A B C
A B D
A E

但是父母的数量不同，矢量的长度也不同。

我想过使用 for 循环，但卡住了，因为我认为我需要树的每个"级别"都有一个，我事先不知道。

我不一定想要代码，只是关于如何处理此类问题的建议！但是任何帮助将不胜感激，谢谢！

编辑：我应该指出，"从头到尾"只是因为我认为这样会更容易 - 这当然没有必要！

数据：

df <- data.frame(Parent = c("A", "B", "B", "A"), Daughter = c("B", "C", "D", "E"))

编辑2：以下是所需结果的更多示例。如果我把桌子大一点，这样：

-------------------------
|  Parent  |  Daughter  |
-------------------------
|     A    |     B      |
|     B    |     C      |
|     B    |     D      |
|     A    |     E      |
|     C    |     F      |
|     C    |     G      |
|     E    |     H      |
|     E    |     I      |
-------------------------

数据 2：

df <- data.frame(Parent = c("A", "B", "B", "A", "C", "C", "E", "E"), Daughter = c("B", "C", "D", "E", "F", "G", "H", "I"))

那么我想要的向量将是：

A B C F
A B C G
A B D
A E H
A E I

Answer 1

使用igraph包，将数据帧转换为图形对象，获取路径，删除属于其他路径子集的路径。

library(igraph)
# example data
df <- data.frame(Parent = c("A", "B", "B", "A", "C", "C", "E", "E"), 
Daughter = c("B", "C", "D", "E", "F", "G", "H", "I"))
# convert to graph object
g <- graph_from_data_frame(df)
# get all the paths, extract node ids from paths
res <- all_simple_paths(g, from = "A")
res <- lapply(res, as_ids)
# get index where vector is not subset of other vector
ix <- sapply(res, function(i) {
x <- sapply(res, function(j) length(intersect(i, j)))
sum(length(i) == x) == 1
})
# result
res <- res[ix]
# res
# [[1]]
# [1] "A" "B" "C" "F"
# 
# [[2]]
# [1] "A" "B" "C" "G"
# 
# [[3]]
# [1] "A" "B" "D"
# 
# [[4]]
# [1] "A" "E" "H"
# 
# [[5]]
# [1] "A" "E" "I"

Answer 2

以下是可能会有所帮助的内容：

parent <- "A"
lev <- df$Daughter[which(df$Parent == parent)]
output <- cbind(parent, lev)
while(length(lev) > 0){
lev <- df$Daughter[which(is.element(df$Parent, lev))]
output <- cbind(output, lev)
}
# which returns
> output
parent lev lev
[1,] "A"    "B" "C"
[2,] "A"    "E" "D"

这可以很容易地翻译成function(parent)：

myfct <- function(parent){
lev <- df$Daughter[which(df$Parent == parent)]
output <- data.frame(parent, lev, stringsAsFactors = F)
while(length(lev) > 0){
dat <- df[which(is.element(df$Parent, lev)),]
newdat <- merge(x = output, y = dat, by.x = "lev", by.y = "Parent", all = TRUE)
col.first <- which(names(newdat) == "parent")
col.last <- which(names(newdat) == "Daughter")
col.sec.last <- which(names(newdat) == "lev")
col.rest <- setdiff(1:dim(newdat)[2], c(col.first, col.sec.last,col.last))
newdat <- newdat[, c(col.first, col.rest, col.sec.last, col.last)]
names(newdat)[2:(length(names(newdat))-1)] <- paste0("x.",2:(length(names(newdat))-1))
names(newdat)[length(names(newdat))] <- "lev" 

output <- newdat
lev <- df$Daughter[which(is.element(df$Parent, lev))]
}
cols <- as.numeric(which(!sapply(output, function(x)all(is.na(x)))))
output <- output[,cols]
return(output)
}

在这里可以应用函数：

parents.list <- unique(df$Parent)
sapply(parents.list, myfct)
# which returns
$A
parent x.2 x.3  x.4
1      A   B   C    F
2      A   B   C    G
3      A   B   D <NA>
4      A   E   H <NA>
5      A   E   I <NA>
$B
parent x.2  x.3
1      B   C    F
2      B   C    G
3      B   D <NA>
$C
parent x.2
1      C   F
2      C   G
$E
parent x.2
1      E   H
2      E   I

现在，您可以随时对其进行修改以更改输出的结构。

---

编辑

关键是要添加一个while。我编辑了我的代码，现在它应该无需指定级别数即可工作。