#![no_std]
#![warn(unused_results, missing_docs)]
#[cfg(feature = "alloc")]
extern crate alloc;
#[cfg(feature = "std")]
extern crate std;
pub mod combinadics;
pub mod factoradics;
pub mod multinadics;
pub mod sequences;
pub fn greatest_common_divisor(mut a: usize, mut b: usize) -> usize {
debug_assert!(a > 0 || b > 0, "Failed precondition");
while b > 0 {
a %= b;
core::mem::swap(&mut a, &mut b);
}
a
}
#[test]
fn greatest_common_divisor_ok() {
fn spec(a: usize, b: usize) -> usize {
let mut r = 0;
for i in 1 ..= std::cmp::max(a, b) {
if a % i == 0 && b % i == 0 {
r = std::cmp::max(r, i);
}
}
r
}
for a in 0 .. 20 {
for b in 0 .. 20 {
if a == 0 && b == 0 {
continue;
}
assert_eq!(greatest_common_divisor(a, b), spec(a, b), "a={a} b={b}");
}
}
}
pub fn factorial(mut n: usize) -> usize {
let mut r = 1;
while n > 0 {
r *= n;
n -= 1;
}
r
}
#[test]
fn factorial_ok() {
fn spec(n: usize) -> usize {
if n == 0 {
1
} else {
n * spec(n - 1)
}
}
for n in 0 .. 10 {
assert_eq!(factorial(n), spec(n), "n={n}");
}
}
pub fn combination(n: usize, k: usize) -> usize {
if n < k {
return 0;
}
let mut r = 1;
let mut d = factorial(k);
for i in 0 .. k {
let mut m = n - i;
if d > 1 {
let g = greatest_common_divisor(m, d);
m /= g;
d /= g;
}
r *= m;
}
debug_assert_eq!(d, 1);
r
}
#[test]
fn combination_ok() {
fn spec(n: usize, k: usize) -> usize {
if k > n {
0
} else {
factorial(n) / (factorial(n - k) * factorial(k))
}
}
for n in 0 .. 5 {
for k in 0 .. 5 {
assert_eq!(combination(n, k), spec(n, k), "n={n} k={k}");
}
}
}
pub fn multinomial<T: Ord>(xs: &[T]) -> usize {
let mut n = xs.len();
let mut r = 1;
for i in 0 .. xs.len() {
if xs[.. i].contains(&xs[i]) {
continue;
}
let k = xs[i ..].iter().filter(|&x| x == &xs[i]).count();
r *= combination(n, k);
n -= k;
}
r
}
#[test]
fn multinomial_ok() {
fn test(xs: &[usize], r: usize) {
assert_eq!(multinomial(xs), r, "xs={xs:?}");
}
test(&[], 1);
test(&[0], 1);
test(&[0, 0], 1);
test(&[0, 1], 2);
test(&[0, 1, 0], 3);
test(&[0, 1, 0, 1], 6);
test(&[0, 1, 1, 0, 2, 0], 60);
}
fn is_ordered_set<T: Ord>(xs: &[T]) -> bool {
xs.windows(2).all(|w| w[0] < w[1])
}
#[test]
fn is_ordered_set_ok() {
fn test(xs: &[usize], r: bool) {
assert_eq!(is_ordered_set(xs), r, "xs={xs:?}");
}
test(&[0, 1], true);
test(&[0, 0], false);
test(&[1, 0], false);
}
fn is_ordered_multiset<T: Ord>(xs: &[T]) -> bool {
xs.windows(2).all(|w| w[0] <= w[1])
}
#[test]
fn is_ordered_multiset_ok() {
fn test(xs: &[usize], r: bool) {
assert_eq!(is_ordered_multiset(xs), r, "xs={xs:?}");
}
test(&[0, 1, 1], true);
test(&[0, 0, 1], true);
test(&[1, 0], false);
}
fn is_unordered_set<T: Ord>(xs: &[T]) -> bool {
xs.iter().all(|x| xs.iter().filter(|&y| x == y).count() == 1)
}
#[test]
fn is_unordered_set_ok() {
fn test(xs: &[usize], r: bool) {
assert_eq!(is_unordered_set(xs), r, "xs={xs:?}");
}
test(&[0, 1], true);
test(&[0, 0], false);
test(&[1, 0], true);
}