SymmetryGroup.order() is O(|G|) — closed-form shortcut for known group families

[spMohanty]

Identified in #67. SymmetryGroup.order() runs _dimino(self._generators) to enumerate all group elements on the first call for a given instance. For S_n that's n!, which becomes infeasible fast:

import time, whest as we
sg = we.SymmetryGroup.symmetric(axes=tuple(range(8)))
t = time.perf_counter()
sg.order()
print(f"S_8 cold: {(time.perf_counter() - t) * 1000:.0f}ms")
# S_8 cold: ~1800ms
t = time.perf_counter()
sg.order()
print(f"S_8 warm: {(time.perf_counter() - t) * 1e6:.1f}μs")
# S_8 warm: ~1μs (cached)

Caching: per-instance, not per-equivalence-class

The result IS memoized on the instance via the _order slot (_perm_group.py:327-331), so subsequent calls on the same SymmetryGroup object are O(1). But the cache is per-instance. Two independently constructed SymmetryGroup.symmetric(axes=(0, ..., 7)) objects each pay the cold cost — and that's exactly the path that hung CI in PR #67's c58454d97 (fixed by ed50c3853): direct_product_groups and restrict_group_to_axes allocate fresh SymmetryGroup instances on every _counted_ufunc_outer / tensordot call, so the composition takes the cold O(|G|) walk every time.

S_9 is 9× worse, S_10 is 90× worse, and S_12 (the per-call cap added in #67's _is_oversized_for_cost_model) hits ~12 minutes on the cold path. PR #67 worked around this by bailing the symmetry-aware cost adjustment above degree 12 and emitting CostFallbackWarning. The bail is correct but it would be better to extend the usable range by computing order() in closed form when the structure is known — every freshly-composed instance would then be cheap regardless of caching.

Suggested approach

When the SymmetryGroup is constructed via a known factory (.symmetric(...), .cyclic(...), .dihedral(...), .identity(...), .young(...), .direct_product(*groups)), tag the resulting object with a _known_kind field and short-circuit order():

Factory	Closed-form order
SymmetryGroup.identity(...)	1
SymmetryGroup.symmetric(axes)	math.factorial(len(axes))
SymmetryGroup.cyclic(axes)	len(axes)
SymmetryGroup.dihedral(axes)	2 * len(axes)
SymmetryGroup.young(blocks)	prod(math.factorial(len(b)) for b in blocks)
SymmetryGroup.direct_product(*groups)	prod(g.order() for g in groups) (recurses; each child must use the shortcut for the chain to be fast)
SymmetryGroup.from_generators(...)	Fall back to _dimino (genuinely unknown structure).

Once order() is fast for known kinds, _is_oversized_for_cost_model's degree-12 cap can be lifted (or replaced with a |G|-based cap, which is the actual quantity that matters for memory in unique_elements_for_shape).

Caveats

• SymmetryGroup.is_symmetric() currently uses order() to check (return self.order() == math.factorial(self._degree)). With the shortcut, is_symmetric() becomes self._known_kind == "symmetric".
• Any _known_kind tag must be invariant under __eq__ — i.e. two equal groups must have the same tag. Easiest invariant: only set the tag from factories; reset to None whenever a group is reconstructed from generators (e.g. from_generators, intersect_groups if it doesn't preserve provenance).
• _known_kind should not be part of the equality contract — equality is purely value-based on the canonical action.

Acceptance criteria

• S_n.order() for n ≤ 20 returns in < 1ms (currently S_8 is ~1.8s).
• Closed-form shortcut tested against _dimino for all factories at small n (e.g. n ≤ 5 for S, n ≤ 8 for D).
• _is_oversized_for_cost_model's threshold raised (or replaced) once the shortcut lands.
• unique_elements_for_shape's Burnside enumeration may also benefit from the same provenance — separate consideration, but related.

Related

• PR Track method calls and NumPy protocols on WhestArray (closes #58, #38, #62) #67 — _is_oversized_for_cost_model + CostFallbackWarning bail; would be partially obsoleted by this fix.
• PR Unify symmetry API around exact SymmetryGroup #51 — perf-class-6 fix (memoize unique_elements_for_shape) — same family of fixes, different call path.
• Issue Intern SymmetryGroup instances by canonical action so equivalent groups share one cache #73 — complementary fix: intern SymmetryGroup instances by canonical action so equivalent groups share one cache. Closed-form order() (this issue) covers known-kind groups; interning (Intern SymmetryGroup instances by canonical action so equivalent groups share one cache #73) covers unknown-kind groups that recur across calls.