#!/usr/bin/env python
#-*- coding: utf-8 -*-
lookup = set()
def recurse(matched, remaining, N=3):
global lookup
# print>>sys.stderr, "recurse:", matched, remaining, N
if len([v for v in matched.values() if v is not None]) == N:
lookup.add(tuple(matched.items()))
else:
for k,v in matched.iteritems():
if v is None:
for r in remaining:
if r != k:
ms = dict(matched)
ms[k] = r
rs = list(remaining)
# rs.remove(r)
recurse(ms, rs, N)
def sz_comp(mapping):
mapping = list(mapping)
if len(mapping) < 1: return 0
grp_no = 0
groups = dict.fromkeys(xrange(1,N+1), None)
visited = dict.fromkeys(xrange(1,N+1), False)
stk = []
while len(mapping) > 0:
a,b = mapping[0]
stk = [a,b]+stk
mapping = mapping[1:]
while len(stk) > 0:
nxt = stk[0]
to_del = []
for f,t in mapping:
if f == nxt:
stk.append(t)
to_del.append((f,t))
elif t == nxt:
stk.append(f)
to_del.append((f,t))
for d in to_del:
mapping.remove(d)
stk = stk[1:]
if visited[nxt]: continue
visited[nxt] = True
groups[nxt] = grp_no
grp_no += 1
max_idx, max_sz = 0, 0
cnt = [0 for i in xrange(grp_no)]
for k,v in groups.iteritems():
cnt[v] += 1
if cnt[v] > max_sz:
max_sz = cnt[v]
max_idx = v
# print groups, max_idx, max_sz
return max_sz
if __name__ == "__main__":
for N in [5]:#xrange(2,7):
# print "=== %d ==="%N
lookup = set()
matches = dict.fromkeys(xrange(1,N+1), None)
recurse(matches, list(xrange(1,N+1)), N)
from pprint import pprint
# pprint(lookup)
# print len(lookup)
from collections import defaultdict
sizes, stats = {}, defaultdict(int)
for mapping in lookup:
sizes[mapping] = sz_comp(mapping)
stats[sz_comp(mapping)] += 1
# pprint(sizes)
# print len(sizes), (N-1)**N
from fractions import Fraction
#ans = Fraction(0)
ans = 0
for k,v in stats.iteritems():
ans += v*k
#ans += Fraction(v*k, len(sizes))
ans = Fraction(ans, len(sizes))
print "%d/%d"%(ans.numerator, ans.denominator)
IyEvdXNyL2Jpbi9lbnYgcHl0aG9uCiMtKi0gY29kaW5nOiB1dGYtOCAtKi0KCmxvb2t1cCA9IHNldCgpCmRlZiByZWN1cnNlKG1hdGNoZWQsIHJlbWFpbmluZywgTj0zKToKCWdsb2JhbCBsb29rdXAKIwlwcmludD4+c3lzLnN0ZGVyciwgInJlY3Vyc2U6IiwgbWF0Y2hlZCwgcmVtYWluaW5nLCBOCglpZiBsZW4oW3YgZm9yIHYgaW4gbWF0Y2hlZC52YWx1ZXMoKSBpZiB2IGlzIG5vdCBOb25lXSkgPT0gTjoKCQlsb29rdXAuYWRkKHR1cGxlKG1hdGNoZWQuaXRlbXMoKSkpCgllbHNlOgoJCWZvciBrLHYgaW4gbWF0Y2hlZC5pdGVyaXRlbXMoKToKCQkJaWYgdiBpcyBOb25lOgoJCQkJZm9yIHIgaW4gcmVtYWluaW5nOgoJCQkJCWlmIHIgIT0gazoKCQkJCQkJbXMgPSBkaWN0KG1hdGNoZWQpCgkJCQkJCW1zW2tdID0gcgoJCQkJCQlycyA9IGxpc3QocmVtYWluaW5nKQoJCQkJCSMJcnMucmVtb3ZlKHIpCgkJCQkJCXJlY3Vyc2UobXMsIHJzLCBOKQoKZGVmIHN6X2NvbXAobWFwcGluZyk6CgltYXBwaW5nID0gbGlzdChtYXBwaW5nKQoJaWYgbGVuKG1hcHBpbmcpIDwgMTogcmV0dXJuIDAKCglncnBfbm8gPSAwCglncm91cHMgPSBkaWN0LmZyb21rZXlzKHhyYW5nZSgxLE4rMSksIE5vbmUpCgl2aXNpdGVkID0gZGljdC5mcm9ta2V5cyh4cmFuZ2UoMSxOKzEpLCBGYWxzZSkKCXN0ayA9IFtdCgl3aGlsZSBsZW4obWFwcGluZykgPiAwOgoJCWEsYiA9IG1hcHBpbmdbMF0KCQlzdGsgPSBbYSxiXStzdGsKCQltYXBwaW5nID0gbWFwcGluZ1sxOl0KCgkJd2hpbGUgbGVuKHN0aykgPiAwOgoJCQlueHQgPSBzdGtbMF0KCQkJdG9fZGVsID0gW10KCQkJZm9yIGYsdCBpbiBtYXBwaW5nOgoJCQkJaWYgZiA9PSBueHQ6CgkJCQkJc3RrLmFwcGVuZCh0KQoJCQkJCXRvX2RlbC5hcHBlbmQoKGYsdCkpCgkJCQllbGlmIHQgPT0gbnh0OgoJCQkJCXN0ay5hcHBlbmQoZikKCQkJCQl0b19kZWwuYXBwZW5kKChmLHQpKQoJCQlmb3IgZCBpbiB0b19kZWw6CgkJCQltYXBwaW5nLnJlbW92ZShkKQoJCQlzdGsgPSBzdGtbMTpdCgkJCWlmIHZpc2l0ZWRbbnh0XTogY29udGludWUKCQkJdmlzaXRlZFtueHRdID0gVHJ1ZQoJCQlncm91cHNbbnh0XSA9IGdycF9ubwoJCWdycF9ubyArPSAxCgoJbWF4X2lkeCwgbWF4X3N6ID0gMCwgMAoJY250ID0gWzAgZm9yIGkgaW4geHJhbmdlKGdycF9ubyldCglmb3Igayx2IGluIGdyb3Vwcy5pdGVyaXRlbXMoKToKCQljbnRbdl0gKz0gMQoJCWlmIGNudFt2XSA+IG1heF9zejoKCQkJbWF4X3N6ID0gY250W3ZdCgkJCW1heF9pZHggPSB2CgojCXByaW50IGdyb3VwcywgbWF4X2lkeCwgbWF4X3N6CglyZXR1cm4gbWF4X3N6CgppZiBfX25hbWVfXyA9PSAiX19tYWluX18iOgoJZm9yIE4gaW4gWzVdOiN4cmFuZ2UoMiw3KToKCQkjIHByaW50ICI9PT0gJWQgPT09IiVOCgkJbG9va3VwID0gc2V0KCkKCQltYXRjaGVzID0gZGljdC5mcm9ta2V5cyh4cmFuZ2UoMSxOKzEpLCBOb25lKQoJCXJlY3Vyc2UobWF0Y2hlcywgbGlzdCh4cmFuZ2UoMSxOKzEpKSwgTikKCQlmcm9tIHBwcmludCBpbXBvcnQgcHByaW50CgkJIyBwcHJpbnQobG9va3VwKQoJCSMgcHJpbnQgbGVuKGxvb2t1cCkKCgkJZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVmYXVsdGRpY3QKCQlzaXplcywgc3RhdHMgPSB7fSwgZGVmYXVsdGRpY3QoaW50KQoJCWZvciBtYXBwaW5nIGluIGxvb2t1cDoKCQkJc2l6ZXNbbWFwcGluZ10gPSBzel9jb21wKG1hcHBpbmcpCgkJCXN0YXRzW3N6X2NvbXAobWFwcGluZyldICs9IDEKCQkjIHBwcmludChzaXplcykKCQkjIHByaW50IGxlbihzaXplcyksIChOLTEpKipOCgoJCWZyb20gZnJhY3Rpb25zIGltcG9ydCBGcmFjdGlvbgoJCSNhbnMgPSBGcmFjdGlvbigwKQoJCWFucyA9IDAKCQlmb3Igayx2IGluIHN0YXRzLml0ZXJpdGVtcygpOgoJCQlhbnMgKz0gdiprCgkJCSNhbnMgKz0gRnJhY3Rpb24odiprLCBsZW4oc2l6ZXMpKQoJCWFucyA9IEZyYWN0aW9uKGFucywgbGVuKHNpemVzKSkKCQlwcmludCAiJWQvJWQiJShhbnMubnVtZXJhdG9yLCBhbnMuZGVub21pbmF0b3IpCg==