CODEWITHSUNDEEP
algorithmcycle-detection
lsund
lsund

Reputation: 744

Cycle detection in non-iterated sequence

My understanding is that tortoise-hare like algorithms works on iterated sequences That is, for any x, succ(x) = x0.

I would like to implement an algortihm that can detect cycles in both deterministic and non-deterministic infinite repeating sequences.

The sequences may have a non-repeating prefix subsequence, for example in the sequence 1666666..., has the prefix of 1 and the repeating pattern 6.

This algorithm would return the longest repeating pattern in a sequence. The repeating pattern of 001100110011... would be 0011, the repeating pattern of 22583575837583758... would be 58357.

My idea was to generate a guess of the longest possible pattern length somehow go from there, but I can't get things in order.

Upvotes: 2

Views: 189

Answers (1)

mksteve
mksteve

Reputation: 13085

The tortoise-hare algorithm uses same address to identify cycles. This problem requires a different sort of algorithm. Some form of trie or structure such as LZW compression, would be where I would look for a solution.

Upvotes: 1

Related Questions