Cycle detection is the algorithmic problem of finding a cycle of the following type:
In mathematics, for any function ƒ that maps a finite set S to itself, and any initial value x0 in S, the sequence of iterated function values
must eventually use the same value twice: there must be some i ≠ j such that xi = xj. Once this happens, the sequence must continue by repeating the cycle of values from xi to xj−1.
The figure shows a function ƒ that maps ...
more
Cycle detection is the algorithmic problem of finding a cycle of the following type:
In mathematics, for any function ƒ that maps a finite set S to itself, and any initial value x0 in S, the sequence of iterated function values
must eventually use the same value twice: there must be some i ≠ j such that xi = xj. Once this happens, the sequence must continue by repeating the cycle of values from xi to xj−1.
The figure shows a function ƒ that maps the set S = {0,1,2,3,4,5,6,7,8} to itself. If one starts from x0 = 2 and repeatedly applies ƒ, one sees the sequence of values
The cycle to be detected is the repeating subsequence of values 6, 3, 1 in this sequence.
Let S be any finite set, ƒ be any function from S to itself, and x0 be any element of S. For any i > 0, let xi = ƒ(xi−1). Let μ be the smallest index such that the value xμ reappears infinitely often within the sequence of values xi, and let λ (the loop length) be the smallest positive integer such that xμ = xλ+μ. The cycle...
less
