rssn 0.2.9

//! # Discrete Groups
//!
//! This module provides implementations for common finite groups, such as
//! cyclic groups (`C_n`), dihedral groups (`D_n`), and symmetric groups (`S_n`).
//! It includes functions to construct these groups and define their multiplication tables.

use std::collections::HashMap;

use crate::symbolic::core::Expr;
use crate::symbolic::group_theory::Group;
use crate::symbolic::group_theory::GroupElement;

/// Creates a cyclic group `C_n` of order `n`.
///
/// The cyclic group is generated by a single element 'g' such that `g^n = e` (the identity).
/// The elements are `{e, g, g^2, ..., g^(n-1)}`. Multiplication is equivalent to addition
/// of exponents modulo `n`.
///
/// # Arguments
/// * `n` - The order of the cyclic group.
///
/// # Returns
/// A `Group` struct representing `C_n`.
#[must_use]
pub fn cyclic_group(n: usize) -> Group {
    let elements: Vec<_> = (0..n)
        .map(|i| {
            if i == 0 {
                GroupElement(Expr::Variable("e".to_string()))
            } else {
                GroupElement(Expr::new_pow(
                    Expr::Variable("g".to_string()),
                    Expr::Variable(i.to_string()),
                ))
            }
        })
        .collect();

    let mut multiplication_table = HashMap::new();

    for i in 0..n {
        for j in 0..n {
            let result_idx = (i + j) % n;

            multiplication_table.insert(
                (elements[i].clone(), elements[j].clone()),
                elements[result_idx].clone(),
            );
        }
    }

    Group::new(elements.clone(), multiplication_table, elements[0].clone())
}

/// Creates a dihedral group `D_n` of order `2n`.
///
/// `D_n` is the group of symmetries of a regular n-gon. It consists of `n` rotations
/// (`r^0, ..., r^(n-1)`) and `n` reflections (`s, sr, ..., sr^(n-1)`).
/// The group is defined by the relations: `r^n = e`, `s^2 = e`, and `s*r = r^(-1)*s`.
///
/// # Arguments
/// * `n` - The number of vertices of the regular polygon.
///
/// # Returns
/// A `Group` struct representing `D_n`.
#[allow(clippy::cast_possible_wrap)]
#[must_use]
pub fn dihedral_group(n: usize) -> Group {
    let mut elements = Vec::with_capacity(2 * n);

    let rotations: Vec<_> = (0..n)
        .map(|i| GroupElement(Expr::Variable(format!("r{i}"))))
        .collect();

    let reflections: Vec<_> = (0..n)
        .map(|i| GroupElement(Expr::Variable(format!("s{i}"))))
        .collect();

    elements.extend(rotations.clone());

    elements.extend(reflections.clone());

    let mut multiplication_table = HashMap::new();

    for i in 0..n {
        for j in 0..n {
            let res_idx = (i + j) % n;

            multiplication_table.insert(
                (rotations[i].clone(), rotations[j].clone()),
                rotations[res_idx].clone(),
            );

            let res_idx = (j as isize - i as isize).rem_euclid(n as isize) as usize;

            multiplication_table.insert(
                (rotations[i].clone(), reflections[j].clone()),
                reflections[res_idx].clone(),
            );

            let res_idx = (i + j) % n;

            multiplication_table.insert(
                (reflections[i].clone(), rotations[j].clone()),
                reflections[res_idx].clone(),
            );

            let res_idx = (j as isize - i as isize).rem_euclid(n as isize) as usize;

            multiplication_table.insert(
                (reflections[i].clone(), reflections[j].clone()),
                rotations[res_idx].clone(),
            );
        }
    }

    Group::new(elements.clone(), multiplication_table, rotations[0].clone())
}

/// Helper function to generate all permutations for `S_n`.
pub(crate) fn generate_permutations(n: usize) -> Vec<Vec<usize>> {
    if n == 0 {
        return vec![vec![]];
    }

    let mut result = Vec::new();

    let mut p: Vec<usize> = (0..n).collect();

    let mut c: Vec<usize> = vec![0; n];

    result.push(p.clone());

    let mut i = 1;

    while i < n {
        if c[i] < i {
            if i % 2 == 0 {
                p.swap(0, i);
            } else {
                p.swap(c[i], i);
            }

            result.push(p.clone());

            c[i] += 1;

            i = 1;
        } else {
            c[i] = 0;

            i += 1;
        }
    }

    result
}

/// Composes two permutations.
/// Permutation multiplication is function composition from right to left.
/// For p1 = [1, 2, 0] and p2 = [0, 2, 1], (p1*p2)(0) = p1(p2(0)) = p1(0) = 1.
pub(crate) fn compose_permutations(
    p1: &[usize],
    p2: &[usize],
) -> Vec<usize> {
    p2.iter().map(|&x| p1[x]).collect()
}

/// Creates a symmetric group `S_n` of order `n!`.
///
/// `S_n` is the group of all permutations of `n` elements. The elements are
/// represented as permutations (e.g., `[1, 2, 0]` for `(0->1, 1->2, 2->0)`).
/// Multiplication is the composition of permutations.
///
/// # Arguments
/// * `n` - The number of elements to permute.
///
/// # Returns
/// A `Group` struct representing `S_n`.
///
/// # Errors
///
/// This function will return an error if a composed permutation cannot be found
/// in the generated group elements, or if the identity element cannot be found.
pub fn symmetric_group(n: usize) -> Result<Group, String> {
    let perms_as_indices = generate_permutations(n);

    let elements: Vec<_> = perms_as_indices
        .iter()
        .map(|p| {
            let expr_vec = p.iter().map(|&i| Expr::Variable(i.to_string())).collect();

            GroupElement(Expr::Vector(expr_vec))
        })
        .collect();

    let mut multiplication_table = HashMap::new();

    for (i, p1_indices) in perms_as_indices.iter().enumerate() {
        for (j, p2_indices) in perms_as_indices.iter().enumerate() {
            let result_indices = compose_permutations(p1_indices, p2_indices);

            let result_idx = match perms_as_indices.iter().position(|p| p == &result_indices) {
                | Some(idx) => idx,
                | None => {
                    return Err("Composed permutation not found in the group elements.".to_string());
                },
            };

            multiplication_table.insert(
                (elements[i].clone(), elements[j].clone()),
                elements[result_idx].clone(),
            );
        }
    }

    let identity_element = match elements.iter().find(|el| {
        if let GroupElement(Expr::Vector(v)) = el {
            v.iter().enumerate().all(|(idx, val)| {
                if let Expr::Variable(s) = val {
                    s.parse::<usize>().unwrap_or(n + 1) == idx
                } else {
                    false
                }
            })
        } else {
            false
        }
    }) {
        | Some(el) => el.clone(),
        | None => {
            return Err("Identity element not found in the symmetric group.".to_string());
        },
    };

    Ok(Group::new(elements, multiplication_table, identity_element))
}

/// Creates the Klein four-group `V_4`.
///
/// `V_4` is an abelian group of order 4, isomorphic to `Z_2` x `Z_2`.
/// Elements: {e, a, b, c}
/// Relations: a^2 = b^2 = c^2 = e, ab = c, bc = a, ca = b.
///
/// # Returns
/// A `Group` struct representing `V_4`.
#[must_use]
pub fn klein_four_group() -> Group {
    let e = GroupElement(Expr::Variable("e".to_string()));

    let a = GroupElement(Expr::Variable("a".to_string()));

    let b = GroupElement(Expr::Variable("b".to_string()));

    let c = GroupElement(Expr::Variable("c".to_string()));

    let elements = vec![e.clone(), a.clone(), b.clone(), c.clone()];

    let mut table = HashMap::new();

    // Identity
    for x in &elements {
        table.insert((e.clone(), x.clone()), x.clone());

        table.insert((x.clone(), e.clone()), x.clone());
    }

    // Squares
    table.insert((a.clone(), a.clone()), e.clone());

    table.insert((b.clone(), b.clone()), e.clone());

    table.insert((c.clone(), c.clone()), e.clone());

    // Products
    table.insert((a.clone(), b.clone()), c.clone());

    table.insert((b.clone(), a.clone()), c.clone());

    table.insert((b.clone(), c.clone()), a.clone());

    table.insert((c.clone(), b.clone()), a.clone());

    table.insert((c.clone(), a.clone()), b.clone());

    table.insert((a, c), b);

    Group::new(elements, table, e)
}