Skip to main content

burnside_orbit_count

Function burnside_orbit_count 

Source
pub fn burnside_orbit_count(models: &[Vec<bool>], group: &[Perm]) -> usize
Expand description

Burnside orbit count — the number of essentially-distinct witnesses. By Burnside’s lemma the number of orbits of a group action equals the average number of fixed points: #orbits = (1/|G|) · Σ_{g∈G} |Fix(g)|, where Fix(g) = { m : g·m = m }. Applied to the solution set (closed under the automorphisms, since every g is an automorphism), this counts the witnesses up to symmetry — the essential solutions — as a fixed-point average, never enumerating an orbit. The sum is exactly divisible by |G| (the lemma guarantees it); group must be the whole group (use perm_group_closure).