/ Published in: Python
Expand |
Embed | Plain Text
Copy this code and paste it in your HTML
def gcd(a,b): """Return the greatest common divisor using Euclid's Algorithm.""" while b: a, b = b, a % b return a def lcm(a,b): return a*(b/gcd(a,b)) def cycle_decomposition(p): n = len(p) cycles = 1 for i in range(n): if p[i]>=0: # if this item has not been visited length = 0 # length of current cycle starting with i j = i # j is the moving index in the cycle starting with i while j!=i or length==0: tmp = j length += 1 j = p[j] p[tmp] = -1 # indicate that this item has been visited #print length cycles = lcm(cycles,length) # print cycles return cycles