How to detect cycles in a vector in R

Question

Let's say I have the following vector:

vec = c(29, 30, 15, 29, 17, 25, 24, 28, 25, 24, 28, 25, 24, 28, 25, 24, 28)

You'll notice there are three repeating elements (25, 24, and 28). How can I get R to recognize when there are repeating elements (or cycles) in a vector? I want to detect this no matter how many elements are repeating (2 or 5 rather than 3) and no matter how many elements into the vector it starts.

For context, I've got an algorithm that is trying to converge on a value, but sometimes it gets stuck in this repeating loop. I want R to detect when it's stuck in this infinite loop and get out. The vec in my example is a log of the value at each iteration.

I've figured out how I can catch double repeating elements (saving the value from the last iteration to compare to the current iteration) but this 3+ repeating elements has me puzzled.

Answer 1

This function will look for patterns of 2 repeated. I calculate a hash of pairs of element [i] with [i+1] by multiplying the second one by "100" and adding to the first one. You can change this factor to some other number, assuming your integers are bounded by that factor. You might want to change this to 1000000. If you have large integers, you may want to rethink this.

Then I look to make sure the hashes are all unique, i.e. the transition from [i] to [i+1] only happens once.

hasCycle <- function(v) {
  hash <- v[1:length(v)-1] + 100 * v[2:length(v)]
  length(unique(hash)) != length(hash)
}

Here's my test

> a <- c(1, 2,3,4,5,1,6,7)
> hasCycle(a)
[1] FALSE
> 
> b <- c(1, 2,3,4,5,9,7,3,4)
> hasCycle(b)
[1] TRUE

Answer 2

Before you run your analysis, use the duplicated() method. If the length of the return vector is 0, then there are no duplicates.

Answer 3

This could work:

If I allow vec to run a bit longer:

vec = c(29, 30, 15, 29, 17, 25, 24, 28, 25, 24, 28, 25, 24, 28, 25, 24, 28, 25, 24, 28, 25, 24, 28, 25, 24, 28, 25, 24, 28, 25, 24, 28)

Then I can find cycles up to 10 elements long with this. Longer cycles can be incorporated by changing 10 but I hopefully will never have to deal with that!

any(sapply(1:10, function(i) all(tail(diff(vec, lag = i), 10) == 0)))