查找子向量0的

Question

我有一個包含假設它的1和0的序列的載體是長度166，並且它是

y <- c(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1, 1,1,1,1,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 
1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,1,1,1,1) 

現在我想提取從上述載體中，使得它滿足兩個屬性

一個最長可能的子矢量

（1）子向量應當從1開始，並用總1.

（2）它可以含有至多5％的零結束子向量的長度。

我以rle函數開始。它在每個步驟計數1和0。 所以它會像

z <- rle(y) 
d <- data.frame(z$values, z$lengths) 
colnames(d) <- c("value", "length") 

它給我

> d 
    value length 
1  1  22 
2  0  1 
3  1  13 
4  0  1 
5  1  2 
6  0  1 
7  1  1 
8  0  1 
9  1  1 
10  0  5 
11  1  1 
12  0  3 
13  1  2 
14  0  1 
15  1  1 
16  0  1 
17  1  74 
18  0  2 
19  1  17 
20  0  1 
21  1  2 
22  0  1 
23  1  3 
24  0  5 
25  1  4 

在這種情況下74 + 17 2 + + 1 + 2 + 3 = 99是所需的子序列，因爲它含有2+ 1 + 1 = 4個零小於99的5％。如果我們向前移動並且序列將變爲99 + 5 + 4 = 108並且零將是4 + 5 = 9，這將會超過108的5％。

Answer 1

我想通過計算這個向量的運行長度編碼，你非常接近。剩下的就是考慮所有的1對運行，並選擇長度最長的一對，並匹配「不超過5％零」規則。

ones <- which(d$value == 1) 
# pairs holds pairs of rows in d that correspond to runs of 1's 
if (length(ones) >= 2) { 
    pairs <- rbind(t(combn(ones, 2)), cbind(ones, ones)) 
} else if (length(ones) == 1) { 
    pairs <- cbind(ones, ones) 
} 

# Taking cumulative sums of the run lengths enables vectorized computation of the lengths 
# of each run in the "pairs" matrix 
cs <- cumsum(d$length) 
pair.length <- cs[pairs[,2]] - cs[pairs[,1]] + d$length[pairs[,1]] 
cs0 <- cumsum(d$length * (d$value == 0)) 
pair.num0 <- cs0[pairs[,2]] - cs0[pairs[,1]] 

# Multiple the length of a pair by an indicator for whether it's valid and take the max 
selected <- which.max(pair.length * ((pair.num0/pair.length) <= 0.05)) 
d[pairs[selected,1]:pairs[selected,2],] 
# value length 
# 15  1  1 
# 16  0  1 
# 17  1  74 
# 18  0  2 
# 19  1  17 
# 20  0  1 
# 21  1  2 
# 22  0  1 
# 23  1  3 

實際上，我們發現子向量稍長就是一個：這可以使用combn計算所有對1和cumsum的奔跑讓遊程的長度從rle輸出完全量化的方式進行OP發現：它有102個元素和5個0（4.90％）。