Объединение векторов неодинаковой длины и неуникальных значений

Я хотел бы сделать следующее:

Объедините в фрейм данных два вектора, которые

  • имеют разную длину
  • содержат последовательности, найденные также в другом векторе
  • содержат последовательности, не найденные в другом векторе
    • Последовательности, которые не найдены в другом векторе, никогда не длиннее 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, чтобы решить эту проблему.

2 4
dataframe missing-data

2 ответа:

Я утверждаю, что ваша задача может быть решена в терминахкратчайшей общей суперсследовательности . Он предполагает, что каждый из ваших двух векторов представляет собой одну последовательность. Пожалуйста, дайте код ниже попробовать.

Если это все еще не решает вашу проблему, вам придется точно объяснить, что вы подразумеваете под "мой вектор содержит не одну, а много последовательностей": определите, что вы подразумеваете под последовательностью и расскажите нам, как последовательности могут быть идентифицированы путем сканирования через ваши два векторные иллюстрации.

Часть I : учитывая две последовательности, найти самую длинную общую подпоследовательность 

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))
}

Часть II : учитывая две последовательности, найти кратчайшую общую суперсеквенцию 

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.)

3

Примечание - это было предложено в качестве ответа на первую версию 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
6