python
from collections import deque,defaultdict
def rbs(s):
    bal=0
    for c in s:
        bal+=1 if c=='(' else -1
        if bal<0:return False
    return bal==0

def subs(s):
    n=len(s)
    res=[]
    for l1 in range(n):
        for r1 in range(l1+1,n+1):
            a=s[l1:r1]
            if not rbs(a): continue
            for l2 in range(r1,n):
                for r2 in range(l2+1,n+1):
                    b=s[l2:r2]
                    if not rbs(b): continue
                    t=s[:l1]+b+s[r1:l2]+a+s[r2:]
                    res.append((l1,r1,l2,r2,t))
    return res

def classes(n):
    from itertools import product
    arr=[''.join(p) for p in product('()', repeat=n) if rbs(''.join(p))]
    seen=set()
    cl=[]
    graph=defaultdict(set)
    for s in arr:
        for *_,t in subs(s):
            graph[s].add(t)
            graph[t].add(s)
    for s in arr:
        if s in seen: continue
        q=[s]; seen.add(s); comp=[]
        while q:
            x=q.pop(); comp.append(x)
            for y in graph[x]:
                if y not in seen:
                    seen.add(y); q.append(y)
        cl.append(sorted(comp))
    return arr,cl
for n in [2,4,6,8]:
    arr,cl=classes(n)
    print("n",n,"count",len(arr),"classes",len(cl),[len(c) for c in cl])
    for c in cl:
        print(c)
    print()

python
s="()()(())"
l1,r1,l2,r2=2,4,5,7
t=s[:l1]+s[l2:r2]+s[r1:l2]+s[l1:r1]+s[r2:]
print(t)

python
from collections import deque
def path(start,target):
    q=deque([start]); par={start:None}
    move={}
    while q:
        s=q.popleft()
        if s==target: break
        n=len(s)
        for l1 in range(n):
            for r1 in range(l1+1,n+1):
                if not rbs(s[l1:r1]): continue
                for l2 in range(r1,n):
                    for r2 in range(l2+1,n+1):
                        if not rbs(s[l2:r2]): continue
                        t=s[:l1]+s[l2:r2]+s[r1:l2]+s[l1:r1]+s[r2:]
                        if t not in par:
                            par[t]=s; move[t]=(l1,r1,l2,r2)
                            q.append(t)
    if target not in

python
def count_adj(s):
    return sum(1 for i in range(len(s)-1) if s[i:i+2]=='()')
for n in [2,4,6,8,10]:
    arr=[''.join(p) for p in __import__('itertools').product('()', repeat=n) if rbs(''.join(p))]
    # compute classes
    from collections import defaultdict
    groups=defaultdict(list)
    for s in arr:
        groups[count_adj(s)].append(s)
    # BFS classes from before maybe expensive for 10 maybe skip
    print(n, {k:len(v) for k,v in groups.items()})

python
from itertools import product
def comps(n):
    arr=[''.join(p) for p in product('()', repeat=n) if rbs(''.join(p))]
    # build graph maybe manageable for 10? 42 states yes
    graph=defaultdict(set)
    for s in arr:
        for *_,t in subs(s):
            graph[s].add(t); graph[t].add(s)
    seen=set(); cls=[]
    for s in arr:
        if s in seen: continue
        q=[s]; seen.add(s); comp=[]
        while q:
            x=q.pop(); comp.append(x)
            for y in graph[x]:
                if y not in seen:
                    seen.add(y); q.append(y)
        cls.append(comp)
    return cls
cls10=comps(10)
print(len(cls10), sorted(len(c)

python
for c in sorted(cls10, key=lambda x:(len(x), min(x))):
    print("size",len(c),"peaks",count_adj(c[0]), sorted(c))
    print()

python
def leaf_depths(s):
    st=[]; depths=[]
    depth=0
    for i,c in enumerate(s):
        if c=='(':
            depth+=1
            st.append(i)
        else:
            j=st.pop()
            if i==j+1:
                depths.append(depth)
            depth-=1
    return tuple(sorted(depths, reverse=True))
for c in sorted(cls10, key=lambda x:(count_adj(x[0]), len(x), min(x))):
    rep=min(c)
    print(rep, "peaks", count_adj(rep), "leafdepths", leaf_depths(rep), "size", len(c))

python
for n in [8]:
    arr,cl=classes(n)
    for c in sorted(cl, key=lambda x:(len(x),min(x))):
        rep=min(c)
        print(rep, len(c), leaf_depths(rep))
        print(sorted(c))
        print()

python
for s in ["()()(())","()(()())","(()())()","(())()()"]:
    print(s, leaf_depths(s))

python
for c in classes(8)[1]:
    print({leaf_depths(s) for s in c}, c)

python
class Node:
    def __init__(self):
        self.children=[]
def parse_forest(s):
    stack=[[]]  # list of forests, stack top is current children list
    for c in s:
        if c=='(':
            stack.append([])
        else:
            ch=stack.pop()
            node=Node(); node.children=ch
            stack[-1].append(node)
    return stack[0]
def leaf_rounds_forest(forest):
    rounds=[]
    cur=forest
    while cur:
        # count leaves in current forest
        def count_leaves(nodes):
            return sum(1 if not nd.children else count_leaves(nd.children) for nd in nodes)
        rounds.append(count_leaves(cur))
        # prune leaves
        def prune(nodes):
            new=[]
            for nd in nodes:
                if nd.children:
                    nd2=Node(); nd2.children=prune(nd.children)
                    new.append(nd2)
            return new
        cur=prune(cur)
    return rounds
for c in classes(8)[1]:
    rr={tuple(leaf_rounds_forest(parse_forest(s))) for s in c}
    print(c, rr)

python
def peak_heights(s):
    bal=0
    res=[]
    for i,c in enumerate(s):
        if c=='(':
            bal+=1
            if i+1<len(s) and s[i+1]==')':
                res.append(bal)
        else:
            bal-=1
    return tuple(res)
for rep in ['(()())(())','((()())())','((()()()))']:
    print(rep, peak_heights(rep))

python
def signature(s):
    forest=parse_forest(s)
    sig=[]
    cur=forest
    while cur:
        counts=[]
        def process(nodes):
            new=[]
            for nd in nodes:
                leafc=sum(1 for ch in nd.children if not ch.children)
                intc=[ch for ch in nd.children if ch.children]
                if nd.children:
                    counts.append(leafc)
                    nd2=Node(); nd2.children=intc  # shallow okay
                    new.append(nd2)
            return new
        # include super-root
        root_leafc=sum(1 for ch in cur if not ch.children)
        root_int=[ch for ch in cur if ch.children]
        counts.append(root_leafc)
        sig.append(tuple(sorted([x for x in counts if x>0], reverse=True)))
        cur=process(root_int)
    return tuple(sig)
for c in classes(8)[1]:
    print(sorted(c), {signature(s) for s in c})

python
def match_arr(s):
    st=[]
    m=[None]*len(s)
    for i,c in enumerate(s):
        if c=='(':
            st.append(i)
        else:
            j=st.pop(); m[i]=j; m[j]=i
    return m
def inv(s):
    m=match_arr(s)
    h=0
    n=len(s)
    while h<n//2 and m[h]==n-1-h:
        h+=1
    p=count_adj(s)
    return p,h
for n in [8,10]:
    arr,cl=classes(n)
    ok=True
    for c in cl:
        vals={inv(s) for s in c}
        if len(vals)!=1:
            ok=False
            print("class not constant",c,vals)
    # compare unique invs count with class count
    print("n",n,"ok",ok,"class count",len(cl),"inv count",len({inv(s) for s in arr}))
    from collections import defaultdict
    grp=defaultdict(list)
    for s in arr:
        grp[inv(s)].append(s)
    # check each inv group connected (equal to some class)
    for key,g in grp.items():
        # see if all g in same class
        cs=[c for c in cl if g[0] in c][0]
        if set(g)!=set(cs):
            print("mismatch",key,set(g)-set(cs),set(cs)-set(g))
            ok=False
            break
    print("final",ok)

python
def do(s,l1,r1,l2,r2):
    return s[:l1]+s[l2:r2]+s[r1:l2]+s[l1:r1]+s[r2:]
s="()(()())"
# prefix first leaf 0..2, inner leaf maybe positions 3..5? let's enumerate RBS substrings and result
n=len(s)
for l1 in range(n):
    for r1 in range(l1+1,n+1):
        if not rbs(s[l1:r1]): continue
        for l2 in range(r1,n):
            for r2 in range(l2+1,n+1):
                if not rbs(s[l2:r2]): continue
                t=do(s,l1,r1,l2,r2)
                if t=="()()(())":
                    print((l1,r1,l2,r2), s[l1:r1], s[l2:r2])