fork download
copy 
  1. # -*- coding: utf-8 -*-
  2.  
  3. from __future__ import print_function
  4. from itertools import islice, cycle, chain, izip, repeat
  5.  
  6.  
  7. def detect_cycle(iterable):
  8.     '''Detect a cycle in iterable object.
  9.     Iterable must return an independend iterator on iter(iterable)'''
  10.  
  11.     tortoise = iter(iterable)
  12.     tortoise_val = next(tortoise)
  13.     hare = islice(iter(iterable),None,None,2)  #two steps at a time
  14.     #it will start from the first value and only then will be advancing 2 values at a time
  15.     hare_val = next(hare)
  16.  
  17.     for tortoise_val, hare_val in izip(tortoise,hare):
  18.         if tortoise_val==hare_val:
  19.             break
  20.  
  21.     hare = tortoise #put hare in the place of tortoise
  22.     hare_val = tortoise_val
  23.     tortoise = iter(iterable) #start tortoise from the very beginning
  24.     tortoise_val = next(tortoise)
  25.     mu = 0
  26.     for tortoise_val, hare_val in chain(repeat((tortoise_val, hare_val),1),izip(tortoise,hare)):
  27.         #begin with the current val of hare.val and the value of tortoise which is in the first position
  28.         if tortoise_val==hare_val:
  29.             break
  30.         mu += 1
  31.  
  32.     lamb = 0
  33.     hare = tortoise
  34.     for hare_val in hare:
  35.         lamb += 1
  36.         if hare_val == tortoise_val: #check AFTER the first step by hare
  37.             break
  38.  
  39.     print('mu: {0}'.format(mu))
  40.     print('lamb: {0}'.format(lamb))
  41.  
  42.  
  43. if __name__ == '__main__':
  44.  
  45.     class iterable(object):
  46.         '''Emulate the object returning iterators having cycles'''
  47.         def __init__(self,beginning,cycling):
  48.             '''
  49. beginning: the beginning part with no cycles (its length corresponds to mu)
  50. cycling: the part which will be cycling (its length corresponds to lamb)
  51. '''
  52.             self.beginning = beginning
  53.             self.cycling = cycling
  54.  
  55.         def __iter__(self):
  56.             return chain(iter(self.beginning),cycle(iter(self.cycling)))
  57.  
  58.     detect_cycle(iterable('1234','678'))
Success #stdin #stdout 0.03s 6712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
mu: 4
lamb: 3
https://ideone.com/fAlML
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!