files / problems / covering / compute / q10 / subgroup_sweep.py
#!/usr/bin/env python3
"""Sweep 2-subgroups of a prescribed group for an invariant radius-2 n-set.
The full automorphism groups of the known optima are too coarse at n = 49 --
Aut(50-set) has orbits of size 1, 2, 16, 64, 128 and the size-<=2 vectors form
a 7-dimensional subspace, so any union of them is trapped there. Subgroups
refine the orbits. This samples subgroups generated by small subsets, and for
each one enumerates the unions of orbits of total size n (exhaustively when
there are few, otherwise up to a cap) and runs the flat syndrome sweep.
Usage: subgroup_sweep.py <listing> <n> [--orders 8,16,32] [--samples N] [--cap N]
"""
import random
import sys
from collections import Counter
sys.path.insert(0, sys.path[0] or ".")
from prescribe_group import apply, close, covers, load, orbits
def union_search(orbs, n, r, cap):
orbs = sorted(orbs, key=lambda o: (-len(o), o[0]))
sizes = [len(o) for o in orbs]
suffix = [0] * (len(orbs) + 1)
for i in range(len(orbs) - 1, -1, -1):
suffix[i] = suffix[i + 1] + sizes[i]
best = [1 << 30, None]
tried = [0]
capped = [False]
def rec(i, total, chosen):
if tried[0] >= cap:
capped[0] = True
return
if total == n:
tried[0] += 1
cols = [x for j in chosen for x in orbs[j]]
h = covers(cols, r)
if h < best[0]:
best[0], best[1] = h, list(chosen)
return
if total > n or i == len(orbs) or total + suffix[i] < n:
return
rec(i + 1, total + sizes[i], chosen + [i])
rec(i + 1, total, chosen)
rec(0, 0, [])
return tried[0], capped[0], best, orbs
def main():
path, n = sys.argv[1], int(sys.argv[2])
orders = [8, 16, 32]
samples, cap = 300, 60000
if "--orders" in sys.argv:
orders = [int(x) for x in sys.argv[sys.argv.index("--orders") + 1].split(",")]
if "--samples" in sys.argv:
samples = int(sys.argv[sys.argv.index("--samples") + 1])
if "--cap" in sys.argv:
cap = int(sys.argv[sys.argv.index("--cap") + 1])
r, S, gens = load(path)
G = sorted(close(gens, r))
rng = random.Random(20260821)
seen, results = set(), {}
total_capped = 0
for _ in range(samples):
k = rng.choice((1, 2, 3))
H = close([rng.choice(G) for _ in range(k)], r)
if len(H) not in orders:
continue
key = frozenset(H)
if key in seen:
continue
seen.add(key)
ho = orbits(H, r)
tried, capped, best, sorted_orbs = union_search(ho, n, r, cap)
total_capped += capped
if best[1] is None:
continue
cur = results.get(len(H), (1 << 30,))[0]
if best[0] < cur:
results[len(H)] = (best[0], len(ho), tried, capped,
[x for j in best[1] for x in sorted_orbs[j]])
if best[0] == 0:
cols = sorted(x for j in best[1] for x in sorted_orbs[j])
print(f"COVERING FOUND, |H|={len(H)}, n={n}:")
print(" ".join(map(str, cols)))
return
print(f"{path}: |G|={len(G)}, {len(seen)} distinct subgroups sampled, "
f"target n={n}")
for order in sorted(results):
holes, norb, tried, capped, _ = results[order]
print(f" |H|={order:>3} orbits={norb:>4} unions tested={tried:>6}"
f"{' (CAPPED, unknown)' if capped else ' (exhaustive)'}"
f" best holes = {holes}")
print(" no covering found -- residue only, not a lower bound")
if __name__ == "__main__":
main()