Cycle detection

From Algorithmist
Jump to navigation Jump to search

The cycle detection algorithm is used to locate repetitions in a sequence of values.

Tortoise and Hare[edit]

The tortoise and hare algoirhtm keeps track of two cycles - the tortoise, which advances one step, and the hare which advances two steps. Once the tortoise and hare match, the tortoise is pulled back to the start of the sequence. The first matching location is determined by the tortoise and hare advancing once each. Once the first match is located, the length is determined by just having the hare advance.

"Mu" referse to the location of the first match, and "Lambda" refers to the length of the cycle.

The algorithms below rely on a transformation function "f". It can be adapted for indexed sequences with a few modifications.

def floyd(f, x0):
    # Main phase of algorithm: finding a repetition x_i = x_2i.
    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then,
    # at some point, the distance between them will be
    # divisible by the period λ.
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
  
    # At this point the tortoise position, ν, which is also equal
    # to the distance between hare and tortoise, is divisible by
    # the period λ. So hare moving in circle one step at a time, 
    # and tortoise (reset to x0) moving towards the circle, will 
    # intersect at the beginning of the circle. Because the 
    # distance between them is constant at 2ν, a multiple of λ,
    # they will agree as soon as the tortoise reaches index μ.

    # Find the position μ of first repetition.    
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        mu += 1
 
    # Find the length of the shortest cycle starting from x_μ
    # The hare moves one step at a time while tortoise is still.
    # lam is incremented until λ is found.
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu

Brent's Algorithm[edit]

Brent's Algorithm is a different version of the tortoise and hare algorithm. It works by having the turtle teleport to powers of 2, and just advancing the hare to see if it matches the tortoise. This determines the length of the cycle.

Once the length is determined, the tortoise and hare are pulled back. The hare gets a head start (equal to cycle length), and both the tortoise and hare advance to find the location of the first match.

# lam = loop length
# mu = first repitition. 

def brent(f, x0):
    # main phase: search successive powers of two
    power = lam = 1
    tortoise = x0
    hare = f(x0) # f(x0) is the element/node next to x0.
    while tortoise != hare:
        if power == lam:   # time to start a new power of two?
            tortoise = hare
            power *= 2
            lam = 0
        hare = f(hare)
        lam += 1
 
    # Find the position of the first repetition of length lambda
    mu = 0
    tortoise = hare = x0
    for i in range(lam):
    # range(lam) produces a list with the values 0, 1, ... , lam-1
        hare = f(hare)
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
 
    return lam, mu


External links[edit]