11

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!

Henrik
  • 65,555
  • 14
  • 143
  • 159
Clara
  • 411
  • 4
  • 13

2 Answers2

13

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.

Clara
  • 411
  • 4
  • 13
  • 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 – Henrik May 08 '19 at 20:23
  • 1
    If you want to keep the first solution in `base`, you may use `head(end, -1)` instead of `lag`. – Henrik May 08 '19 at 20:37
  • @Henrik 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! – Clara May 23 '19 at 20:56
  • 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 – Henrik May 23 '19 at 22:49
  • 1
    Also without `lag`: `start <- end - rle_x$lengths + 1` – qwr Jun 26 '19 at 20:07
10

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
Jaap
  • 81,064
  • 34
  • 182
  • 193
Henrik
  • 65,555
  • 14
  • 143
  • 159