1#!/usr/bin/env python3
  2"""Canonical orbit search for symmetric subset masks.
  3
  4Indices are zero based.  A permutation is a tuple p with p[i] the image of i.
  5"""
  6import itertools, json, math, time
  7from collections import Counter
  8
  9
 10def lex_key(s):
 11    return tuple(s)
 12
 13
 14def apply_perm(s, p):
 15    return tuple(sorted(p[i] for i in s))
 16
 17
 18def is_canonical(s, group):
 19    s = tuple(sorted(s))
 20    return all(apply_perm(s, p) >= s for p in group)
 21
 22
 23def canonical(s, group):
 24    return min(apply_perm(s, p) for p in group)
 25
 26
 27def all_permutations(n):
 28    return list(itertools.permutations(range(n)))
 29
 30
 31def compose(p, q):
 32    return tuple(p[q[i]] for i in range(len(p)))
 33
 34
 35def group_generated(n, generators):
 36    """Small closure by BFS; useful for non-full symmetry groups."""
 37    identity = tuple(range(n))
 38    seen = {identity}
 39    todo = [identity]
 40    while todo:
 41        a = todo.pop()
 42        for b in generators:
 43            c = compose(a, b)
 44            if c not in seen:
 45                seen.add(c); todo.append(c)
 46    return sorted(seen)
 47
 48
 49def product_block_group(blocks):
 50    """Direct product of full symmetric groups on disjoint blocks."""
 51    n = sum(len(b) for b in blocks)
 52    choices = [list(itertools.permutations(b)) for b in blocks]
 53    out = []
 54    for parts in itertools.product(*choices):
 55        p = list(range(n))
 56        for block, perm in zip(blocks, parts):
 57            for x, y in zip(block, perm): p[x] = y
 58        out.append(tuple(p))
 59    return out
 60
 61
 62def exhaustive(n, k, group):
 63    masks = list(itertools.combinations(range(n), k))
 64    reps = [s for s in masks if is_canonical(s, group)]
 65    return masks, reps
 66
 67
 68def canonical_dfs(n, k, group):
 69    visited = []
 70    calls = 0
 71    def dfs(s):
 72        nonlocal calls
 73        calls += 1
 74        if len(s) == k:
 75            visited.append(tuple(s)); return
 76        start = s[-1] + 1 if s else 0
 77        for i in range(start, n):
 78            t = tuple(s) + (i,)
 79            if is_canonical(t, group):
 80                dfs(t)
 81    dfs(())
 82    return visited, calls
 83
 84
 85def predecessor_check(n, k, group):
 86    reps = [s for s in itertools.combinations(range(n), k) if is_canonical(s, group)]
 87    bad = []
 88    for s in reps:
 89        if s and not is_canonical(s[:-1], group): bad.append((s, s[:-1]))
 90    return len(reps), bad
 91
 92
 93def invariant_score(s, group, seed=7):
 94    """A deterministic score invariant under the supplied group.
 95    Each orbit receives a score; this models exact symmetry of a mask evaluator.
 96    """
 97    # Hash orbit representative, rather than individual mask, makes symmetry exact.
 98    c = canonical(s, group)
 99    x = (seed * 1000003 + sum((j + 1) * (i + 11) for j, i in enumerate(c))) % 10000019
100    return 0.5 + (x / 10000019)
101
102
103def main():
104    # Core smallest useful checks, including a nontrivial block-product symmetry.
105    checks = []
106    groups = [
107        ("S6", all_permutations(6)),
108        ("S3xS3", product_block_group([tuple(range(3)), tuple(range(3, 6))])),
109        ("cyclic6", group_generated(6, [(1,2,3,4,5,0)])),
110    ]
111    for name, g in groups:
112        n = 6
113        for k in range(1, n):
114            reps, bad = predecessor_check(n, k, g)
115            assert not bad, (name, k, bad[:1])
116            masks, exhaustive_reps = exhaustive(n, k, g)
117            dfs_reps, calls = canonical_dfs(n, k, g)
118            assert set(dfs_reps) == set(exhaustive_reps)
119            # Every mask is in exactly one orbit, and reps are orbit count.
120            assert len({canonical(s, g) for s in masks}) == len(exhaustive_reps)
121        checks.append({"group": name, "group_size": len(g), "predecessor_closure": True})
122
123    # Mini experiment: exact symmetry means all masks in an orbit have identical score.
124    n, k = 12, 6
125    g = all_permutations(n)
126    t0 = time.perf_counter()
127    masks = list(itertools.combinations(range(n), k))
128    exhaustive_scores = [invariant_score(s, g) for s in masks]
129    exhaustive_time = time.perf_counter() - t0
130    t0 = time.perf_counter()
131    reps, calls = canonical_dfs(n, k, g)
132    canonical_scores = [invariant_score(s, g) for s in reps]
133    canonical_time = time.perf_counter() - t0
134    best_exhaustive = max(exhaustive_scores)
135    best_canonical = max(canonical_scores)
136    assert len(reps) == 1
137    assert best_exhaustive == best_canonical
138    assert all(invariant_score(s, g) == invariant_score(reps[0], g) for s in masks)
139
140    # A second, less degenerate symmetry pattern gives multiple orbit representatives.
141    gb = product_block_group([tuple(range(6)), tuple(range(6, 12))])
142    mb, rb = exhaustive(n, k, gb)
143    db, block_calls = canonical_dfs(n, k, gb)
144    assert set(rb) == set(db)
145    result = {
146        "math_checks": checks,
147        "mini_experiment": {
148            "n": n, "k": k, "all_masks": len(masks),
149            "exhaustive_representatives": len(set(canonical(s, g) for s in masks)),
150            "canonical_representatives": len(reps),
151            "canonical_dfs_nodes": calls,
152            "exhaustive_seconds": exhaustive_time,
153            "canonical_seconds": canonical_time,
154            "speedup_observed": exhaustive_time / canonical_time,
155            "best_score_exhaustive": best_exhaustive,
156            "best_score_canonical": best_canonical,
157            "best_scores_equal": best_exhaustive == best_canonical,
158        },
159        "block_symmetry": {
160            "group_size": len(gb), "all_masks": len(mb),
161            "orbit_representatives": len(rb), "dfs_representatives": len(db),
162            "dfs_nodes": block_calls,
163        },
164    }
165    print(json.dumps(result, indent=2, sort_keys=True))
166
167if __name__ == "__main__": main()