在R中的数字序列中找到具有特定长度的所有子序列

Question

我想找到（最小）长度为n的序列中的所有子序列。假设我有这个顺序

sequence <- c(1,2,3,2,5,3,2,6,7,9)

我想找到最小长度为3的递增子序列。输出应该是每个找到的子序列具有开始和结束位置的数据框。

df =data.frame(c(1,7),c(3,10))
colnames(df) <- c("start", "end")

有人可以提示如何解决我的问题吗？

提前致谢！

Answer 1

仅使用基本 R 的一种方法

n <- 3

do.call(rbind, sapply(split(1:length(sequence), cumsum(c(0, diff(sequence)) < 1)), 
        function(x) if (length(x) >= n) c(start = x[1], end = x[length(x)])))

#  start end
#1    1    3
#4    7   10

splitsequence基于连续增量子序列的索引，如果length每个组的 大于等于，则n返回该组的开始和结束索引。

为了理解，让我们分解并逐步理解它

使用diff我们可以找到连续元素之间的差异

diff(sequence)
#[1]  0  1  1 -1  3 -2 -1  4  1  2

我们检查其中哪些不具有递增子序列

diff(sequence) < 1
#[1] FALSE FALSE  TRUE FALSE  TRUE  TRUE FALSE FALSE FALSE

并对它们求和以创建组

cumsum(c(0, diff(sequence)) < 1)
#[1] 1 1 1 2 2 3 4 4 4 4

基于这些组，我们的split索引来自1:length(sequence)

split(1:length(sequence), cumsum(c(0, diff(sequence)) < 1))
#$`1`
#[1] 1 2 3

#$`2`
#[1] 4 5

#$`3`
#[1] 6

#$`4`
#[1]  7  8  9 10

使用sapply我们循环这个列表并返回列表的开始和结束索引if（在本例中length为>= n3）

sapply(split(1:length(sequence), cumsum(c(0, diff(sequence)) < 1)), 
       function(x) if (length(x) >= n) c(start = x[1], end = x[length(x)]))

#$`1`
#start   end 
#    1     3 

#$`2`
# NULL

#$`3`
#NULL

#$`4`
#start   end 
#    7    10 

最后，rbind他们一起使用do.call. NULL元素会被自动忽略。

do.call(rbind, sapply(split(1:length(sequence), cumsum(c(0, diff(sequence)) < 1)), 
       function(x) if (length(x) >= n) c(start = x[1], end = x[length(x)])))

#  start end
#1     1   3
#4     7  10