Posted By

bingjian on 08/01/09


Tagged

algorithm permutation cycledecomposition


Versions (?)

Cycle Decomposition


 / Published in: Python
 

  1. def gcd(a,b):
  2. """Return the greatest common divisor using Euclid's Algorithm."""
  3. while b:
  4. a, b = b, a % b
  5. return a
  6.  
  7. def lcm(a,b):
  8. return a*(b/gcd(a,b))
  9.  
  10. def cycle_decomposition(p):
  11. n = len(p)
  12. cycles = 1
  13. for i in range(n):
  14. if p[i]>=0: # if this item has not been visited
  15. length = 0 # length of current cycle starting with i
  16. j = i # j is the moving index in the cycle starting with i
  17. while j!=i or length==0:
  18. tmp = j
  19. length += 1
  20. j = p[j]
  21. p[tmp] = -1 # indicate that this item has been visited
  22. #print length
  23. cycles = lcm(cycles,length) #
  24. print cycles
  25. return cycles

Report this snippet  

You need to login to post a comment.