CODEWITHSUNDEEP
rsubsequence
ClementWalter
ClementWalter

Reputation: 5272

Extract an increasing subsequence

I wish to extract an increasing subsequence of a vector, starting from the first element. For example, from this vector:
a = c(2, 5, 4, 0, 1, 6, 8, 7)

...I'd like to return:
res = c(2, 5, 6, 8).

I thought I could use a loop, but I want to avoid it. Another attempt with sort:

a = c(2, 5, 4, 0, 1, 6, 8, 7)
ind = sort(a, index.return = TRUE)$ix
mat = (t(matrix(ind))[rep(1, length(ind)), ] - matrix(ind)[ , rep(1, length(ind))])
mat = ((mat*upper.tri(mat)) > 0) %*% rep(1, length(ind)) == (c(length(ind):1) - 1)
a[ind][mat]

Basically I sort the input vector and check if the indices verify the condition "no indices at the right hand side are lower" which means that there were no greater values beforehand.

But it seems a bit complicated and I wonder if there are easier/quicker solutions, or a pre-built function in R.

Thanks

Upvotes: 4

Views: 663

Answers (2)

JohannesNE
JohannesNE

Reputation: 1363

The other answer is better, but i made this iterative function which works as well. It works by making all consecutive differences > 0

  increasing <- function (input_vec) {
      while(!all(diff(input_vec) > 0)){
          input_vec <- input_vec[c(1,diff(input_vec))>0]
      }
      input_vec
  }

Upvotes: 1

Henrik
Henrik

Reputation: 67778

One possibility would be to find the cumulative maxima of the vector, and then extract unique elements:

unique(cummax(a))
# [1] 2 5 6 8

Upvotes: 10

Related Questions