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.     hare = islice(iter(iterable),None,None,2)  #two steps at a time
  13.     #it will start from the first value and only then will be advancing 2 values at a time
  14.  
  15.     for tortoise_val, hare_val in islice(izip(tortoise,hare),1,None): #skip the first value
  16.         if tortoise_val==hare_val:
  17.             break
  18.  
  19.     hare = tortoise #put hare in the place of tortoise
  20.     hare_val = tortoise_val
  21.     tortoise = iter(iterable) #start tortoise from the very beginning
  22.     mu = 0
  23.     for tortoise_val, hare_val in izip(tortoise,chain(repeat(hare_val,1),hare)):
  24.         #begin with the current val of hare.val and the value of tortoise which is in the first position
  25.         if tortoise_val==hare_val:
  26.             break
  27.         mu += 1
  28.  
  29.     lamb = 0
  30.     hare = tortoise
  31.     for hare_val in hare:
  32.         lamb += 1
  33.         if hare_val == tortoise_val: #check AFTER the first step by hare
  34.             break
  35.  
  36.     print('mu: {0}'.format(mu))
  37.     print('lamb: {0}'.format(lamb))
  38.  
  39.  
  40. if __name__ == '__main__':
  41.  
  42.     class iterable(object):
  43.         '''Emulate the object returning iterators having cycles'''
  44.         def __init__(self,beginning,cycling):
  45.             '''
  46. beginning: the beginning part with no cycles (its length corresponds to mu)
  47. cycling: the part which will be cycling (its length corresponds to lamb)
  48. '''
  49.             self.beginning = beginning
  50.             self.cycling = cycling
  51.  
  52.         def __iter__(self):
  53.             return chain(iter(self.beginning),cycle(iter(self.cycling)))
  54.  
  55.     detect_cycle(iterable('1234','678'))
  56.  
Success #stdin #stdout 0.03s 6400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
mu: 4
lamb: 3
https://ideone.com/vJKiv
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!