fork download
copy 
  1. #!/usr/bin/env python
  2. #-*- coding: utf-8 -*-
  3.  
  4. lookup = set()
  5. def recurse(matched, remaining, N=3):
  6. 	global lookup
  7. #	print>>sys.stderr, "recurse:", matched, remaining, N
  8. 	if len([v for v in matched.values() if v is not None]) == N:
  9. 		lookup.add(tuple(matched.items()))
  10. 	else:
  11. 		for k,v in matched.iteritems():
  12. 			if v is None:
  13. 				for r in remaining:
  14. 					if r != k:
  15. 						ms = dict(matched)
  16. 						ms[k] = r
  17. 						rs = list(remaining)
  18. 					#	rs.remove(r)
  19. 						recurse(ms, rs, N)
  20.  
  21. def sz_comp(mapping):
  22. 	mapping = list(mapping)
  23. 	if len(mapping) < 1: return 0
  24.  
  25. 	grp_no = 0
  26. 	groups = dict.fromkeys(xrange(1,N+1), None)
  27. 	visited = dict.fromkeys(xrange(1,N+1), False)
  28. 	stk = []
  29. 	while len(mapping) > 0:
  30. 		a,b = mapping[0]
  31. 		stk = [a,b]+stk
  32. 		mapping = mapping[1:]
  33.  
  34. 		while len(stk) > 0:
  35. 			nxt = stk[0]
  36. 			to_del = []
  37. 			for f,t in mapping:
  38. 				if f == nxt:
  39. 					stk.append(t)
  40. 					to_del.append((f,t))
  41. 				elif t == nxt:
  42. 					stk.append(f)
  43. 					to_del.append((f,t))
  44. 			for d in to_del:
  45. 				mapping.remove(d)
  46. 			stk = stk[1:]
  47. 			if visited[nxt]: continue
  48. 			visited[nxt] = True
  49. 			groups[nxt] = grp_no
  50. 		grp_no += 1
  51.  
  52. 	max_idx, max_sz = 0, 0
  53. 	cnt = [0 for i in xrange(grp_no)]
  54. 	for k,v in groups.iteritems():
  55. 		cnt[v] += 1
  56. 		if cnt[v] > max_sz:
  57. 			max_sz = cnt[v]
  58. 			max_idx = v
  59.  
  60. #	print groups, max_idx, max_sz
  61. 	return max_sz
  62.  
  63. if __name__ == "__main__":
  64. 	for N in [5]:#xrange(2,7):
  65. 		# print "=== %d ==="%N
  66. 		lookup = set()
  67. 		matches = dict.fromkeys(xrange(1,N+1), None)
  68. 		recurse(matches, list(xrange(1,N+1)), N)
  69. 		from pprint import pprint
  70. 		# pprint(lookup)
  71. 		# print len(lookup)
  72.  
  73. 		from collections import defaultdict
  74. 		sizes, stats = {}, defaultdict(int)
  75. 		for mapping in lookup:
  76. 			sizes[mapping] = sz_comp(mapping)
  77. 			stats[sz_comp(mapping)] += 1
  78. 		# pprint(sizes)
  79. 		# print len(sizes), (N-1)**N
  80.  
  81. 		from fractions import Fraction
  82. 		#ans = Fraction(0)
  83. 		ans = 0
  84. 		for k,v in stats.iteritems():
  85. 			ans += v*k
  86. 			#ans += Fraction(v*k, len(sizes))
  87. 		ans = Fraction(ans, len(sizes))
  88. 		print "%d/%d"%(ans.numerator, ans.denominator)
  89.  
Success #stdin #stdout 0.67s 8904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
155/32
https://ideone.com/eK9c9Z
language:
Python (cpython 2.7.16)
created:
10 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!