Tortoise and hare cycle detection algorithm using iterators in Python

Question

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?

Answer 1

# -*- 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))

• ovgolovin: Thank you for suggestions. I have updated the code. Here it is: ideone.com/fYZ35. About the independence of iterators. I think it's very important. But I only came up with adding a warning in the description. Because I can't use itertools.tee since it'll defeat all the benefits of using this algorithm (since it'll be storing all the intermediary values). Also the usage of chain(repeat((tortoise.val, hare.val),1)... looks particularly ugly for me. But I haven't found any other way to add a single value to the chain.
• ovgolovin: I've made another version of the code which uses no class: ideone.com/fAlML All the logic which used to be covered in the code is no scattered around the code (the calculation of the first value follows a new iterator initialization always). Still, I don't like the code. The only conclusion I can draw from the experiment is that the original version of the code operating with indexes is more clear, short and straightforward.
• ovgolovin: Update 1: ideone.com/vJKiv Still curious, if it's the best way to add a single value before the main iterator: chain(repeat(hare_val,1),hare) (here hare_val is added befor all the other values returned by hare iterator).
• ovgolovin: Update 2: ideone.com/fgrwM Put all while True: code fragments into the function. Had to bring back the holding iterator class since otherwise I would have to return the current values of the iterator from that function somehow which will make the code completely cumbersome.
• Winston Ewert: @ovgolovin, instead of repeat(hare_val, 1) just use [hare_val]. What if consume_iterator... returned the matching value as well as the count? I think then you can get rid of keeping iterator.