4

我想做以下事情：

组合成一个数据框，两个向量

  • 有不同的长度
  • 包含在另一个向量中也发现的序列
  • 包含在其他向量中找不到的序列
  • 在其他向量中找不到的序列永远不会超过 3 个元素
  • 总是有相同的第一个元素

数据框应显示对齐的两个向量中的相等序列，如果一个向量缺少另一个向量中存在的序列，则在列中显示 NA。

例如：

vector 1    vector 2                     vector 1        vector 2
   1           1                            a               a
   2           2                            g               g
   3           3                            b               b
   4           1            or              h               a
   1           2                            a               g
   2           3                            g               b   
   5           4                            c               h
               5                                            c

应该组合成数据框

    1   1                                    a   a
    2   2                                    g   g
    3   3                                    b   b
    4   NA                                   h   NA
    1   1                  or                a   a 
    2   2                                    g   g
    NA  3                                    NA  b
    NA  4                                    NA  h
    5   5                                    c   c

我所做的是搜索合并、组合、cbind、plyr 示例，但无法找到解决方案。恐怕我需要开始编写一个带有嵌套 for 循环的函数来解决这个问题。

4

2 回答 2

6

注意- 这是作为对第一版 OP 的回答而提出的。从那时起，该问题已被修改，但我认为该问题仍未明确定义。

这是一个适用于您的integer示例并且也适用于numeric向量的解决方案。我还假设：

  • 两个向量包含相同数量的序列
  • 一个新的序列从哪里开始value[i+1] <= value[i]

如果您的向量不是数字的，或者我的假设之一不适合您的问题，您必须澄清。

v1 <- c(1,2,3,4,1,2,5)
v2 <- c(1,2,3,1,2,3,4,5)

v1.sequences <- split(v1, cumsum(c(TRUE, diff(v1) <= 0)))
v2.sequences <- split(v2, cumsum(c(TRUE, diff(v2) <= 0)))

align.fun <- function(s1, s2) { #aligns two sequences
  s12 <- sort(unique(c(s1, s2)))
  cbind(ifelse(s12 %in% s1, s12, NA),
        ifelse(s12 %in% s2, s12, NA))
}

do.call(rbind, mapply(align.fun, v1.sequences, v2.sequences))
#       [,1] [,2]
#  [1,]    1    1
#  [2,]    2    2
#  [3,]    3    3
#  [4,]    4   NA
#  [5,]    1    1
#  [6,]    2    2
#  [7,]   NA    3
#  [8,]   NA    4
#  [9,]    5    5
于 2012-12-15T21:47:37.157 回答
3

我认为您的问题可能会根据最短的公共超序列来解决。它假设您的两个向量分别代表一个序列。请尝试下面的代码。

如果它仍然不能解决您的问题，您必须准确解释“我的向量包含的不是一个而是多个序列”的含义：定义序列的含义并告诉我们如何通过扫描您的序列来识别序列两个向量。

第一部分：给定两个序列，找到最长的公共子序列

LongestCommonSubsequence <- function(X, Y) {
    m <- length(X)
    n <- length(Y)
    C <- matrix(0, 1 + m, 1 + n)
    for (i in seq_len(m)) {
        for (j in seq_len(n)) {
            if (X[i] == Y[j]) {
                C[i + 1, j + 1] = C[i, j] + 1
            } else {
                C[i + 1, j + 1] = max(C[i + 1, j], C[i, j + 1])
            }
        }
    }

    backtrack <- function(C, X, Y, i, j) {
        if (i == 1 | j == 1) {
            return(data.frame(I = c(), J = c(), LCS = c()))
        } else if (X[i - 1] == Y[j - 1]) {
            return(rbind(backtrack(C, X, Y, i - 1, j - 1),
                         data.frame(LCS = X[i - 1], I = i - 1, J = j - 1)))
        } else if (C[i, j - 1] > C[i - 1, j]) {
            return(backtrack(C, X, Y, i, j - 1))
        } else {
            return(backtrack(C, X, Y, i - 1, j))
        }
    }

    return(backtrack(C, X, Y, m + 1, n + 1))
}

第二部分：给定两个序列，找到最短的公共超序列

ShortestCommonSupersequence <- function(X, Y) {
    LCS <- LongestCommonSubsequence(X, Y)[c("I", "J")]
    X.df <- data.frame(X = X, I = seq_along(X), stringsAsFactors = FALSE)
    Y.df <- data.frame(Y = Y, J = seq_along(Y), stringsAsFactors = FALSE)   
    ALL <- merge(LCS, X.df, by = "I", all = TRUE)
    ALL <- merge(ALL, Y.df, by = "J", all = TRUE)
    ALL <- ALL[order(pmax(ifelse(is.na(ALL$I), 0, ALL$I),
                          ifelse(is.na(ALL$J), 0, ALL$J))), ]
    ALL$SCS <- ifelse(is.na(ALL$X), ALL$Y, ALL$X)
    ALL
}

你的例子：

ShortestCommonSupersequence(X = c("a","g","b","h","a","g","c"),
                            Y = c("a","g","b","a","g","b","h","c"))
#    J  I    X    Y SCS
# 1  1  1    a    a   a
# 2  2  2    g    g   g
# 3  3  3    b    b   b
# 9 NA  4    h <NA>   h
# 4  4  5    a    a   a
# 5  5  6    g    g   g
# 6  6 NA <NA>    b   b
# 7  7 NA <NA>    h   h
# 8  8  7    c    c   c

（其中两个更新的向量在列X和Y中。）

于 2012-12-16T04:15:21.213 回答