Revision: 16362
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at August 1, 2009 18:54 by bingjian
Initial Code
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
Initial URL
Initial Description
Initial Title
Cycle Decomposition
Initial Tags
Initial Language
Python