alkahest-cas 3.12.0

//! Standard families of permutation groups, in their natural degree-`n` action.
//!
//! Each of these returns a group on the points `{0, …, n−1}` (or `{0, …, n}`
//! where noted) whose order is known in closed form, which is what makes them
//! the first thing to test a Schreier–Sims implementation against:
//! `|S_n| = n!`, `|A_n| = n!/2`, `|C_n| = n`, `|D_n| = 2n`.

use super::{GroupError, Permutation, PermutationGroup};

/// The trivial group on `degree` points.
pub fn trivial(degree: usize) -> PermutationGroup {
    PermutationGroup::new(degree, Vec::new()).expect("no generators, so no degree to mismatch")
}

/// The symmetric group `S_n` on `{0, …, n−1}`. `|S_n| = n!`.
///
/// Generated by the transposition `(0 1)` together with the `n`-cycle
/// `(0 1 … n−1)`. `S_0` and `S_1` are trivial and `S_2` is generated by the
/// transposition alone.
pub fn symmetric(n: usize) -> Result<PermutationGroup, GroupError> {
    let mut generators = Vec::new();
    if n >= 2 {
        generators.push(Permutation::from_cycles(n, &[vec![0, 1]])?);
    }
    if n >= 3 {
        generators.push(Permutation::from_cycles(n, &[(0..n).collect()])?);
    }
    PermutationGroup::new(n, generators)
}

/// The alternating group `A_n` on `{0, …, n−1}`. `|A_n| = n!/2` for `n ≥ 2`.
///
/// Generated by the 3-cycle `(0 1 2)` and a long cycle: `(0 1 … n−1)` for odd
/// `n`, `(1 2 … n−1)` for even `n` — in both cases an *even* permutation, which
/// is the point. `A_0`, `A_1` and `A_2` are trivial.
pub fn alternating(n: usize) -> Result<PermutationGroup, GroupError> {
    let mut generators = Vec::new();
    if n >= 3 {
        generators.push(Permutation::from_cycles(n, &[vec![0, 1, 2]])?);
    }
    if n >= 4 {
        let long: Vec<usize> = if n % 2 == 1 {
            (0..n).collect()
        } else {
            (1..n).collect()
        };
        generators.push(Permutation::from_cycles(n, &[long])?);
    }
    PermutationGroup::new(n, generators)
}

/// The cyclic group `C_n` in its regular action on `{0, …, n−1}`. `|C_n| = n`.
///
/// Refuses `n = 0`: the trivial group has order 1, not 0, so there is no
/// faithful degree-0 action to call `C_0`.
pub fn cyclic(n: usize) -> Result<PermutationGroup, GroupError> {
    if n == 0 {
        return Err(GroupError::UnsupportedDegree {
            family: "cyclic",
            requested: n,
            reason: "n must be at least 1; there is no group of order 0",
        });
    }
    let generators = if n == 1 {
        Vec::new()
    } else {
        vec![Permutation::from_cycles(n, &[(0..n).collect()])?]
    };
    PermutationGroup::new(n, generators)
}

/// The dihedral group `D_n` — the symmetries of a regular `n`-gon, acting on
/// its `n` vertices. **`|D_n| = 2n`**, the convention in which `D_3 ≅ S_3`.
///
/// Generated by the rotation `(0 1 … n−1)` and the reflection `i ↦ −i mod n`.
///
/// Refuses `n < 3` ([`GroupError::UnsupportedDegree`]). `D_1` and `D_2` exist
/// as abstract groups — of orders 2 and 4 — but their degree-`n` action on 1
/// or 2 vertices is not faithful, so what this function would return is not
/// the group its name promises. Returning a group of the wrong order under the
/// right name is exactly the silent-wrong-answer failure this crate refuses;
/// build the Klein four-group on four points by hand if that is what you want.
pub fn dihedral(n: usize) -> Result<PermutationGroup, GroupError> {
    if n < 3 {
        return Err(GroupError::UnsupportedDegree {
            family: "dihedral",
            requested: n,
            reason: "the action of D_n on n vertices is faithful only for n >= 3; for n = 1 \
                     or 2 it would return a group of order less than 2n",
        });
    }
    let rotation = Permutation::from_cycles(n, &[(0..n).collect()])?;
    let reflection = Permutation::from_images((0..n).map(|i| (n - i) % n).collect())?;
    PermutationGroup::new(n, vec![rotation, reflection])
}