neumann/matrix_game/polynomial/
helper.rs

1//! This module is mainly for internal usage.
2
3use ndarray::Array2;
4use polynomials::{poly, Polynomial};
5
6/// Returns the determinant as a polynomial.
7///
8/// # Complexity
9///
10/// It involves computing `n!` products of polynomials.
11pub fn determinant(poly_array: &Array2<Polynomial<i32>>) -> Polynomial<i32> {
12    if poly_array.shape() == &[1, 1] {
13        poly_array[[0, 0]].clone()
14    } else {
15        (0..poly_array.shape()[1])
16            .map(|j| {
17                if (j % 2) == 0 {
18                    poly_array[[0, j]].clone() * determinant(&reduce_coordinate(poly_array, 0, j))
19                } else {
20                    poly_array[[0, j]].clone()
21                        * (-1)
22                        * determinant(&reduce_coordinate(poly_array, 0, j))
23                }
24            })
25            .fold(poly![0], |acc, p| acc + p)
26    }
27}
28
29/// Returns the determinant of the sub-matrix without a row and a column, with the corresponding sign.
30///
31/// If `row + column` is odd, then it returns minus the determinant, if it is even, the determinant.
32pub fn cofactor(
33    poly_array: &Array2<Polynomial<i32>>,
34    row: usize,
35    column: usize,
36) -> Polynomial<i32> {
37    if (row + column) % 2 == 0 {
38        determinant(&reduce_coordinate(poly_array, row, column))
39    } else {
40        determinant(&reduce_coordinate(poly_array, row, column)) * (-1)
41    }
42}
43
44/// Returns a sub-array by eliminating the corresponding row and column.
45fn reduce_coordinate(
46    poly_array: &Array2<Polynomial<i32>>,
47    row: usize,
48    column: usize,
49) -> Array2<Polynomial<i32>> {
50    let original_shape = [poly_array.shape()[0], poly_array.shape()[1]];
51    let mut sub_poly_array = Vec::new();
52    for i in 0..original_shape[0] {
53        for j in 0..original_shape[1] {
54            if !((i == row) || (j == column)) {
55                sub_poly_array.push(poly_array[[i, j]].clone())
56            }
57        }
58    }
59    Array2::from_shape_vec(
60        (original_shape[0] - 1, original_shape[1] - 1),
61        sub_poly_array,
62    )
63    .unwrap()
64}
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69    use ndarray::array;
70    use polynomials::poly;
71    use test_case::test_case;
72
73    #[test_case(array![[poly![1, 0], poly![0, 2]], [poly![1, 0], poly![1, 1]]], poly![1, -1] ; "linear")]
74    #[test_case(array![[poly![1, 1], poly![0, 1]], [poly![1, 0], poly![0, 1]]], poly![0, 0, 1] ; "quadratic")]
75    fn computing_determinant(poly_array: Array2<Polynomial<i32>>, expected: Polynomial<i32>) {
76        assert_eq!(determinant(&poly_array), expected);
77    }
78
79    #[test_case(array![[poly![1, 0], poly![0, 2]], [poly![1, 0], poly![1, 1]]], 0, 0, poly![1, 1] ; "Two by two linear polynomials [0, 0]")]
80    #[test_case(array![[poly![1, 0], poly![0, 2]], [poly![1, 0], poly![1, 1]]], 0, 1, poly![-1, 0] ; "Two by two linear polynomials [0, 1]")]
81    #[test_case(array![[poly![1, 0], poly![0, 2]], [poly![1, 0], poly![1, 1]]], 1, 0, poly![0, -2] ; "Two by two linear polynomials [1, 0]")]
82    #[test_case(array![[poly![1, 0], poly![0, 2]], [poly![1, 0], poly![1, 1]]], 1, 1, poly![1, 0] ; "Two by two linear polynomials [1, 1]")]
83    fn computing_cofactor(
84        poly_array: Array2<Polynomial<i32>>,
85        row: usize,
86        column: usize,
87        expected: Polynomial<i32>,
88    ) {
89        assert_eq!(cofactor(&poly_array, row, column), expected);
90    }
91
92    #[test_case(array![[poly![1, 0], poly![0, 2]], [poly![1, 0], poly![1, 1]]], 0, 0, array![[poly![1, 1]]] ; "Two by two linear polynomials [0, 0]")]
93    #[test_case(array![[poly![1, 0], poly![0, 2]], [poly![1, 0], poly![1, 1]]], 0, 1, array![[poly![1, 0]]] ; "Two by two linear polynomials [0, 1]")]
94    #[test_case(array![[poly![1, 0], poly![0, 2]], [poly![1, 0], poly![1, 1]]], 1, 0, array![[poly![0, 2]]] ; "Two by two linear polynomials [1, 0]")]
95    #[test_case(array![[poly![1, 0], poly![0, 2]], [poly![1, 0], poly![1, 1]]], 1, 1, array![[poly![1, 0]]] ; "Two by two linear polynomials [1, 1]")]
96    fn reducing_coordinate(
97        poly_array: Array2<Polynomial<i32>>,
98        row: usize,
99        column: usize,
100        expected: Array2<Polynomial<i32>>,
101    ) {
102        assert_eq!(reduce_coordinate(&poly_array, row, column), expected);
103    }
104}
neumann/matrix_game/polynomial/helper.rs

neumann/matrix_game/polynomial/
helper.rs
