one-indexed-vec 0.2.0

A one-based (1-indexed) wrapper around Vec<T>: element at position N is accessed via vec[N].
Documentation
//! Combinatorics: factorials, binomial coefficients, permutations.

use crate::Vec1;

impl Vec1<u128> {
    /// All binomial coefficients for `(x + y)^n`, 1-based.
    ///
    /// `out[k+1] = C(n, k)`.
    ///
    /// ```rust
    /// use one_indexed_vec::Vec1;
    /// let row = Vec1::<u128>::binomial_row(5);
    /// assert_eq!(row[1], 1);   // C(5, 0)
    /// assert_eq!(row[3], 10);  // C(5, 2)
    /// assert_eq!(row[6], 1);   // C(5, 5)
    /// ```
    pub fn binomial_row(n: usize) -> Self {
        let mut out = Self::with_capacity(n + 1);
        for k in 0..=n {
            out.push(binomial(n, k));
        }
        out
    }
}

// ============================================================================
// Scalar functions
// ============================================================================

/// Factorial `n!`. Saturates at `u128::MAX`.
///
/// ```rust
/// use one_indexed_vec::math::combinatorics::factorial;
/// assert_eq!(factorial(0), 1);
/// assert_eq!(factorial(5), 120);
/// ```
pub fn factorial(n: usize) -> u128 {
    let mut r: u128 = 1;
    for i in 2..=n {
        r = r.saturating_mul(i as u128);
    }
    r
}

/// Binomial coefficient `C(n, k)`.
///
/// ```rust
/// use one_indexed_vec::math::combinatorics::binomial;
/// assert_eq!(binomial(5, 2), 10);
/// assert_eq!(binomial(10, 3), 120);
/// assert_eq!(binomial(3, 5), 0);
/// ```
pub fn binomial(n: usize, k: usize) -> u128 {
    if k > n {
        return 0;
    }
    let k = k.min(n - k);
    let mut r: u128 = 1;
    for i in 0..k {
        r = r * (n - i) as u128 / (i + 1) as u128;
    }
    r
}

/// Permutations `P(n, k) = n! / (n-k)!`.
///
/// ```rust
/// use one_indexed_vec::math::combinatorics::permutations;
/// assert_eq!(permutations(5, 2), 20);
/// assert_eq!(permutations(3, 5), 0);
/// ```
pub fn permutations(n: usize, k: usize) -> u128 {
    if k > n {
        return 0;
    }
    let mut r: u128 = 1;
    for i in 0..k {
        r = r.saturating_mul((n - i) as u128);
    }
    r
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn factorial_basic() {
        assert_eq!(factorial(0), 1);
        assert_eq!(factorial(1), 1);
        assert_eq!(factorial(5), 120);
        assert_eq!(factorial(10), 3628800);
    }

    #[test]
    fn binomial_basic() {
        assert_eq!(binomial(5, 0), 1);
        assert_eq!(binomial(5, 2), 10);
        assert_eq!(binomial(10, 3), 120);
        assert_eq!(binomial(3, 5), 0);
        assert_eq!(binomial(5, 5), 1);
    }

    #[test]
    fn binomial_row_basic() {
        let row = Vec1::<u128>::binomial_row(5);
        assert_eq!(row.len(), 6);
        assert_eq!(row[1], 1);
        assert_eq!(row[3], 10);
        assert_eq!(row[6], 1);
    }

    #[test]
    fn permutations_basic() {
        assert_eq!(permutations(5, 2), 20);
        assert_eq!(permutations(3, 5), 0);
        assert_eq!(permutations(5, 5), 120);
    }
}