代码之家 › 专栏 › 技术社区 › Serhii

与两列连接表一致的序列事件

data-manipulation data.table r

Serhii · 技术社区 · 7 年前

library(data.table)
df = data.table(p1 = c("x0", "x0", "x1", "x2", "x3"),
                p2 = c("x1", "x2", "x3", "x3", "x4"))

下面是一个示例:

只有在所有以前的事件都已经发生的情况下,下一个事件才可能发生。例如,事件x3可能仅在x1和x2之后发生,而与它们的顺序无关。

df_required = data.table(p = c("x0", "x1", "x2", "x3", "x4", 
                               "x0", "x1", "x2", "x3", "x4"),
                         sequence = c(1, 2, 3, 4, 5, 1, 3, 2, 4, 5),
                         group = c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2))

所需表格显示了两组可能的连接:x0-x1-x2-x3-x4和x0-x2-x1-x3-x4。有两种可能的方法,因为两个值可能紧跟在x0:x1或x2之后。顺序也写在图中圆圈的上方。

2 回复 | 直到 7 年前

Frank 7 年前

你可以给每个节点分配一个等级(假设你有 a graph for which this makes any sense

vdf = data.table(p = sort(unique(unlist(df[, c("p1", "p2")]))))

i = 0L
vdf[, r := 0L]
while (any(vdf[r == i, p] %in% df$p1)){
  vdf[r == i, r := r + !df[.(p), on=.(p1), p %in% setdiff(p1, p2)]]
  i = i + 1L
}

    p r
1: x0 0
2: x1 1
3: x2 1
4: x3 2
5: x4 3

如果有特别的第一件事, x0

library(igraph)
vdf[, r := as.vector(distances(graph_from_data_frame(df), "x0"))]

然后,对于每个具有多个节点的列组,采用所有排列(这里,借用 Generating all distinct permutations of a list in R

wdf = vdf[, do.call(cbind, lapply(split(.I, r), function(x) as.data.table(
  gtools::permutations(length(x), length(x), x)
)))]

   0.V1 1.V1 1.V2 2.V1 3.V1
1:    1    2    3    4    5
2:    1    3    2    4    5

中的值 wdf ?.I vdf ,所以。。。

mdf = melt(wdf[, g := .I], id = "g", value.name = "w")[order(g, variable)]
vdf[mdf$w, .(p, g = mdf$g, r)][, seq := rowid(g)][]

     p g r seq
 1: x0 1 0   1
 2: x1 1 1   2
 3: x2 1 1   3
 4: x3 1 2   4
 5: x4 1 3   5
 6: x0 2 0   1
 7: x2 2 1   2
 8: x1 2 1   3
 9: x3 2 2   4
10: x4 2 3   5

所以呢 g 是OP中提到的“组”; r seq 是组中的序列(非常有用,因此表的排序是显式的)。

评论。 将rank/depth属性分配给 虚拟磁盘 . 所有关于可行事件序列的信息都在这里,但是枚举它们(如在OP的输出中)在计算时间和空间方面可能非常昂贵,因此如果可能的话应该避免。

事件的排列数 x factorial(length(x)) ,例如长度为10,返回的矩阵具有维度 dim(gtools::permutations(10, 10)) =3628800 x 10。我的计算机在尝试计算时挂起。

Andre Elrico 7 年前

我只是发布这个,因为它给出了与Rolands建议相同的输出:

(如果没有意义,我就把它去掉)

数据:

library(data.table)
df = data.table(p1 = c("x0", "x0", "x1", "x2", "x3"),
                p2 = c("x1", "x2", "x3", "x3", "x4"))

代码:

restElements <- setdiff(df$p1, df$p2)
ans <-
    t(do.call(
        expand.grid, c(restElements, unique(split(df$p2,df$p1)))
        ))

group = rep(1:ncol(ans), each = nrow(ans))

p     = c( ans )

sequence = as.numeric(factor(p))

data.table(p, sequence, group)

结果:

#    p sequence group
#1: x0        1     1
#2: x1        2     1
#3: x3        4     1
#4: x4        5     1
#5: x0        1     2
#6: x2        3     2
#7: x3        4     2
#8: x4        5     2

请注意:

factor(p) ,得到正确的顺序(默认情况下,因子级别只是排序。适用于此示例,但可能不适用于其他示例。)
而不是我的 ans

因此您可以将两者结合起来:

借用@罗兰

lvls <- levels(factor(c(df$p1, df$p2)))
library(igraph);
tmp <- lapply(all_shortest_paths(graph_from_data_frame(df), lvls[1], lvls[length(lvls)])$res, as.vector)
ans <- sapply(tmp, function(x) { lvls[x] })

答案 . 确保以后使用: sequence = as.numeric(factor(p, lvls))