Find pediodicity in a list

slate slate is offline Offline Jan 20th, 2009, 5:29 pm |
0
A brute force method.
Finds the FIRST and SHORTEST periodicity in the input list.
Quick reply to this message  
Python Syntax
  1. def find_period(inp):
  2. '''
  3. Finds the FIRST and SHORTEST periodicity in the list: inp.
  4. Returns the position of the 0-based begin of the periodicity if any, and the length of it
  5. If it does not find any, returns None
  6. '''
  7. pos=0
  8. other=1
  9. adjust=0
  10. leninp=len(inp)
  11. while pos<leninp:
  12. try:
  13. other=inp.index(inp[pos],pos+1+adjust)
  14. except ValueError:
  15. other=None
  16. if other and other-pos<=leninp-other:
  17. for i in xrange(other,leninp):
  18. if inp[i-(other-pos)]!=inp[i]:
  19. adjust+=1
  20. break
  21. else:
  22. return pos, other-pos
  23. else:
  24. adjust=0
  25. pos+=1

Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC