Tortoise and hare cycle detection algorithm using iterators in Python Reading the article in Wikipedia about cycle detection I came across a relatively small code snipped of Floyd's cycle-finding algorithm. I'll put it here to keep everything in one place:

def floyd(f, x0):
    # The main phase of the algorithm, finding a repetition x_mu = x_2mu
    # The hare moves twice as quickly as the tortoise
    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 start of the loop is equi-distant from current tortoise
    # position and x0, so hare moving in circle and tortoise (set to x0 )
    # moving towards circle, will intersect at the beginning of the circle.

    # Find the position of the first repetition of length mu
    # The hare and tortoise move at the same speeds
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1

    # Find the length of the shortest cycle starting from x_mu
    # The hare moves while the tortoise stays still
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1

    return lam, mu


But then I decided, why not rewrite this algorithm using iterators.

The result wasn't as good as I had hoped it to be.

In some parts of the code I needed the values that the iterators have already returned. So I had keep the values apart from iterators themselves. And I introduced the class animal to keep them in one place.

To my mind, the code got very hefty and ugly. Here it is:

# -*- coding: utf-8 -*-

from __future__ import print_function
from itertools import islice,cycle,chain


def detect_cycle(iterable):

    class animal(object):
        '''Holds the iterator and keeps the last value returned by the iterator'''
        def __init__(self,iterable):          
            self.it = iter(iterable)
            self.value = next(self.it) #get the first value

        def next(self):
            self.value = next(self.it)
            return self.value

        def __iter__(self):
            return self


    tortoise = animal(iterable)
    hare = animal(islice(iter(iterable),None,None,2))  #two steps at a time

    while True:
        if next(tortoise) == next(hare):
            break

    hare = tortoise #put hare in the place of tortoise
    tortoise = animal(iterable) #start tortoise from the very beginning
    mu = 0
    while True:
        if hare.value == tortoise.value:
            break
        next(hare)
        next(tortoise)
        mu += 1


    lamb = 0
    tortoise_val = tortoise.value #save the value of tortoise as the object is reassigned to hare
    hare = tortoise
    while True:
        next(hare)
        lamb += 1
        if hare.value == tortoise_val: #check AFTER the first step by hare
            break

    print('mu: {}'.format(mu))
    print('lamb: {}'.format(lamb))


if __name__ == '__main__':

    class iterable(object):
        '''Emulate the object returning iterators having cycles'''
        def __init__(self,beginning,cycling):
            '''
beginning: the beginning part with no cycles (its length corresponds to mu)
cycling: the part which will be cycling (its length corresponds to lamb)
'''
            self.beginning = beginning
            self.cycling = cycling

        def __iter__(self):
            return chain(iter(self.beginning),cycle(iter(self.cycling)))

    detect_cycle(iterable('1234','678'))


Is there anything that can be done to improve the code?
Is it the best that can be done using iterators?
# -*- coding: utf-8 -*-

from __future__ import print_function
from itertools import islice,cycle,chain


def detect_cycle(iterable):

    class animal(object):


Putting classes inside function is usually not all that helpful. Also, the name doesn't really suggest what this class does. 

        '''Holds the iterator and keeps the last value returned by the iterator'''
        def __init__(self,iterable):          
            self.it = iter(iterable)


I'd do something like iter, just because it isn't a really obvious abbreviation

            self.value = next(self.it) #get the first value

        def next(self):
            self.value = next(self.it)
            return self.value

        def __iter__(self):
            return self


    tortoise = animal(iterable)
    hare = animal(islice(iter(iterable),None,None,2))  #two steps at a time


You end up create two iterators from the same iterable. That might be problematic as you can't be sure those two iterators are independent.

    while True:
        if next(tortoise) == next(hare):
            break


You get most of the benefit of iterators when you can use for loops. In this case, I might use a for loop with itertools.izip.

    hare = tortoise #put hare in the place of tortoise
    tortoise = animal(iterable) #start tortoise from the very beginning
    mu = 0
    while True:
        if hare.value == tortoise.value:
            break
        next(hare)
        next(tortoise)
        mu += 1


You do this basic thing three times. You loop through both iterators, until they match. Write a function that takes the two iterators, does that and then returns the count of them.

    lamb = 0
    tortoise_val = tortoise.value #save the value of tortoise as the object is reassigned to hare
    hare = tortoise
    while True:
        next(hare)
        lamb += 1
        if hare.value == tortoise_val: #check AFTER the first step by hare
            break

    print('mu: {}'.format(mu))
    print('lamb: {}'.format(lamb))