fork(1) download
copy 
  1.  
  2. def multiply_perm(p1, p2):
  3. 	assert len(p1) == len(p2)
  4. 	result = [None] * len(p1)
  5. 	for i in xrange(len(p1)):
  6. 		result[i] = p2[p1[i]]
  7. 	return result
  8.  
  9. def inverse_perm(p):
  10. 	result = [None] * len(p)
  11. 	for i, p_i in enumerate(p):
  12. 		print i, p_i
  13. 		result[p_i] = i
  14. 	assert None not in result
  15. 	return result
  16.  
  17. def cycle_decompose_perm(p):
  18. 	visited = [False] * len(p)
  19. 	for i in xrange(len(p)):
  20. 		if visited[i]:
  21. 			continue
  22. 		cur_cycle = []
  23. 		pos = i
  24. 		while not visited[pos]:
  25. 			visited[pos] = True
  26. 			cur_cycle.append(pos)
  27. 			pos = p[pos]
  28. 		yield cur_cycle
  29.  
  30. def gcd(a, b):
  31. 	if not a and not b:
  32. 		return 1
  33. 	while b:
  34. 		a, b = b, a % b
  35. 	return a
  36.  
  37. def lcm(a, b):
  38. 	return (a / gcd(a, b)) * b
  39.  
  40. def find_power_of_perm(p):
  41. 	ans = 1
  42. 	for cyc in cycle_decompose_perm(p):
  43. 		ans = lcm(ans, len(cyc))
  44. 	return ans
  45.  
  46. assert multiply_perm([0,1,2,3], [1,2,3,0]) == [1,2,3,0]
  47. assert inverse_perm([2,0,1]) == [1,2,0]
  48. assert list(cycle_decompose_perm([1,0,3,2])) == [[0,1], [2,3]]
  49. assert find_power_of_perm([0,1,2,3]) == 1
  50. assert find_power_of_perm([1,0,3,2]) == 2
  51. assert find_power_of_perm([1,2,3,0]) == 4
Success #stdin #stdout 0s 9024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0OllG0
language:
Python (cpython 2.7.16)
created:
9 years ago
visibility:
public

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!