Find start and end positions/indices of runs/consecutive values

Question

Problem: Given an atomic vector, find the start and end indices of runs in the vector.

Example vector with runs:

x = rev(rep(6:10, 1:5))
# [1] 10 10 10 10 10  9  9  9  9  8  8  8  7  7  6

Output from rle():

rle(x)
# Run Length Encoding
#  lengths: int [1:5] 5 4 3 2 1
#  values : int [1:5] 10 9 8 7 6

Desired output:

#   start end
# 1     1   5
# 2     6   9
# 3    10  12
# 4    13  14
# 5    15  15

The base rle class doesn't appear to provide this functionality, but the class Rle and function rle2 do. However, given how minor the functionality is, sticking to base R seems more sensible than installing and loading additional packages.

There are examples of code snippets (here, here and on SO) which solve the slightly different problem of finding start and end indices for runs which satisfy some condition. I wanted something that would be more general, could be performed in one line, and didn't involve the assignment of temporary variables or values.

Answering my own question because I was frustrated by the lack of search results. I hope this helps somebody!

Poff

Answer 1

Core logic:

# Example vector and rle object
x = rev(rep(6:10, 1:5))
rle_x = rle(x)

# Compute endpoints of run
end = cumsum(rle_x$lengths)
start = c(1, lag(end)[-1] + 1)

# Display results
data.frame(start, end)
#   start end
# 1     1   5
# 2     6   9
# 3    10  12
# 4    13  14
# 5    15  15

Tidyverse/dplyr way (data frame-centric):

library(dplyr)

rle(x) %>%
  unclass() %>%
  as.data.frame() %>%
  mutate(end = cumsum(lengths),
         start = c(1, dplyr::lag(end)[-1] + 1)) %>%
  magrittr::extract(c(1,2,4,3)) # To re-order start before end for display

Because the start and end vectors are the same length as the values component of the rle object, solving the related problem of identifying endpoints for runs meeting some condition is straightforward: filter or subset the start and end vectors using the condition on the run values.

Poff

Hi @Clara! I have some problems running your code. In your first solution, do you mean dplyr::lag? In your second solution, do mean select instead of extract (from tidyr?) ? Cheers – Leadin

If you want to keep the first solution in base, you may use head(end, -1) instead of lag. – Leadin

@Leadin Good question! I meant stats::lag (I also recently ran into a problem with namespace collision between dplyr and stats on lag, so understand why you would ask!). For extract, I mean magrittr::extract, which is a forward pipe-friendly function for the [ operator. Thank you for calling those ambiguities out, I hadn't realized at the time what I was doing! – Poff

Thanks for your response @Clara! With stats::lag I get a different result than what you show. (start <- c(1, stats::lag(end)[-1] + 1)); [1] 1 10 13 15 16. dplyr::lag gives the result you show though: (start <- c(1, dplyr::lag(end)[-1] + 1)); [1] 1 6 10 13 15. Cheers – Leadin

Also without lag: start <- end - rle_x$lengths + 1 – Brawley

Answer 2

A data.table possibility, where .I and .N are used to pick relevant indices, per group defined by rleid runs.

library(data.table)
data.table(x)[ , .(start = .I[1], end = .I[.N]), by = rleid(x)][, rleid := NULL][]
#    start end
# 1:     1   5
# 2:     6   9
# 3:    10  12
# 4:    13  14
# 5:    15  15

Leadin