Struct Comb 

pub struct Comb<M: Module> { /* private fields */ }

Useful struct to compute combinations

Examples

use algonium::math::{Comb, Mod107, Mint107};
let comb: Comb<Mod107> = Comb::new(100);
assert_eq!(Mint107::from(24), comb.fact(4));
assert_eq!(Mint107::from(1), comb.fact(4) * comb.factinv(4));
assert_eq!(Mint107::from(12), comb.perm(4, 2));
assert_eq!(Mint107::from(6), comb.comb(4, 2));
assert_eq!(Mint107::from(10), comb.multi_comb(4, 2));

Implementations

impl<M: Module> Comb<M>

pub fn new(n: usize) -> Comb<M>

Create a object that provides effiecint computation of combinations for input smaller than n.

This requires O(n) time.

pub fn fact(&self, n: u64) -> Mint<M>

n! = 1 * 2 * ... * n

O(1) if n is smaller than input in new method.

pub fn factinv(&self, n: u64) -> Mint<M>

returns y such that n! * y == 1.

O(1) if n is smaller than input in new method.

pub fn perm(&self, n: u64, r: u64) -> Mint<M>

nPr = n! / (n - r)!

O(1) if n and r are smaller than input in new method.

pub fn comb(&self, n: u64, r: u64) -> Mint<M>

nCr = n! / (n - r)! / r!.

O(1) if n and r are smaller than input in new method.

pub fn multi_comb(&self, n: u64, r: u64) -> Mint<M>

(n + k - 1)! / k!.

O(1) if n and r are smaller than input in new method.