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?
