competitive::math

Struct Matrix

Source 
pub struct Matrix<T> {
    pub shape: (usize, usize),
    pub data: Vec<Vec<T>>,
}

Fields§

§shape: (usize, usize)§data: Vec<Vec<T>>

Implementations§

Source§

impl<T: Clone> Matrix<T>

Source

pub fn new(shape: (usize, usize), z: T) -> Self

Source§

impl<T> Matrix<T>

Source

pub fn from_vec(data: Vec<Vec<T>>) -> Self

Examples found in repository?
crates/competitive/src/algorithm/esper.rs (line 76)
69    pub fn solve(self) -> EsperSolver<T, Input, Class, FC, FF> {
70        let data: HashMap<_, _> = self
71            .data
72            .into_iter()
73            .map(|(key, (a, b))| {
74                (
75                    key,
76                    Matrix::from_vec(a).solve_system_of_linear_equations(&b),
77                )
78            })
79            .collect();
80        EsperSolver {
81            class: self.class,
82            feature: self.feature,
83            data,
84            _marker: PhantomData,
85        }
86    }
87
88    pub fn solve_checked(self) -> EsperSolver<T, Input, Class, FC, FF>
89    where
90        Class: Debug,
91        T: Debug,
92    {
93        let data: HashMap<_, _> = self
94            .data
95            .into_iter()
96            .map(|(key, (a, b))| {
97                let mat = Matrix::from_vec(a);
98                let coeff = mat.solve_system_of_linear_equations(&b);
99                if coeff.is_none() {
100                    eprintln!(
101                        "failed to solve linear equations: key={:?} A={:?} b={:?}",
102                        key, &mat.data, &b
103                    );
104                }
105                (key, coeff)
106            })
107            .collect();
108        EsperSolver {
109            class: self.class,
110            feature: self.feature,
111            data,
112            _marker: PhantomData,
113        }
114    }
More examples
Hide additional examples
crates/competitive/src/math/matrix.rs (lines 227-229)
215    pub fn inverse(&self) -> Option<Matrix<T>> {
216        assert_eq!(self.shape.0, self.shape.1);
217        let n = self.shape.0;
218        let mut c = Matrix::<T>::zeros((n, n * 2));
219        for i in 0..n {
220            c[i][..n].clone_from_slice(&self[i]);
221            c[i][n + i] = T::one();
222        }
223        c.row_reduction(true);
224        if (0..n).any(|i| c[i][i].is_zero()) {
225            None
226        } else {
227            Some(Self::from_vec(
228                c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
229            ))
230        }
231    }
Source§

impl<T> Matrix<T>
where T: Clone + Zero,

Source

pub fn zeros(shape: (usize, usize)) -> Self

Examples found in repository?
crates/competitive/src/math/matrix.rs (line 78)
76    fn add(self, rhs: Self) -> Self::Output {
77        assert_eq!(self.shape, rhs.shape);
78        let mut res = Matrix::zeros(self.shape);
79        for i in 0..self.shape.0 {
80            for j in 0..self.shape.1 {
81                res[i][j] = self[i][j] + rhs[i][j];
82            }
83        }
84        res
85    }
86}
87impl<T> Sub for &Matrix<T>
88where
89    T: Copy + Zero + Sub<Output = T>,
90{
91    type Output = Matrix<T>;
92    fn sub(self, rhs: Self) -> Self::Output {
93        assert_eq!(self.shape, rhs.shape);
94        let mut res = Matrix::zeros(self.shape);
95        for i in 0..self.shape.0 {
96            for j in 0..self.shape.1 {
97                res[i][j] = self[i][j] - rhs[i][j];
98            }
99        }
100        res
101    }
102}
103impl<T> Mul for &Matrix<T>
104where
105    T: Copy + Zero + Add<Output = T> + Mul<Output = T>,
106{
107    type Output = Matrix<T>;
108    fn mul(self, rhs: Self) -> Self::Output {
109        assert_eq!(self.shape.1, rhs.shape.0);
110        let mut res = Matrix::zeros((self.shape.0, rhs.shape.1));
111        for i in 0..self.shape.0 {
112            for j in 0..rhs.shape.1 {
113                for k in 0..self.shape.1 {
114                    res[i][j] = res[i][j] + self[i][k] * rhs[k][j];
115                }
116            }
117        }
118        res
119    }
120}
121impl<T> Matrix<T>
122where
123    T: Copy + Zero + One + Add<Output = T> + Mul<Output = T>,
124{
125    pub fn pow(&self, mut n: usize) -> Self {
126        assert_eq!(self.shape.0, self.shape.1);
127        let mut x = self.clone();
128        let mut res = Matrix::eye(self.shape);
129        while n > 0 {
130            if n & 1 == 1 {
131                res = &res * &x;
132            }
133            x = &x * &x;
134            n >>= 1;
135        }
136        res
137    }
138}
139impl<T> Matrix<T>
140where
141    T: Copy + PartialEq + Zero + One + Sub<Output = T> + Mul<Output = T> + Div<Output = T>,
142{
143    pub fn row_reduction(&mut self, normalize: bool) {
144        let (n, m) = self.shape;
145        let mut c = 0;
146        for r in 0..n {
147            loop {
148                if c >= m {
149                    return;
150                }
151                if let Some(pivot) = (r..n).find(|&p| !self[p][c].is_zero()) {
152                    self.data.swap(r, pivot);
153                    break;
154                };
155                c += 1;
156            }
157            let d = T::one() / self[r][c];
158            if normalize {
159                for j in c..m {
160                    self[r][j] = self[r][j] * d;
161                }
162            }
163            for i in (0..n).filter(|&i| i != r) {
164                let mut e = self[i][c];
165                if !normalize {
166                    e = e * d;
167                }
168                for j in c..m {
169                    self[i][j] = self[i][j] - e * self[r][j];
170                }
171            }
172            c += 1;
173        }
174    }
175    pub fn rank(&mut self) -> usize {
176        let n = self.shape.0;
177        self.row_reduction(false);
178        (0..n)
179            .filter(|&i| !self.data[i].iter().all(|x| x.is_zero()))
180            .count()
181    }
182    pub fn determinant(&mut self) -> T {
183        assert_eq!(self.shape.0, self.shape.1);
184        self.row_reduction(false);
185        let mut d = T::one();
186        for i in 0..self.shape.0 {
187            d = d * self[i][i];
188        }
189        d
190    }
191    pub fn solve_system_of_linear_equations(&self, b: &[T]) -> Option<Vec<T>> {
192        assert_eq!(self.shape.0, b.len());
193        let (n, m) = self.shape;
194        let mut c = Matrix::<T>::zeros((n, m + 1));
195        for i in 0..n {
196            c[i][..m].clone_from_slice(&self[i]);
197            c[i][m] = b[i];
198        }
199        c.row_reduction(true);
200        let mut x = vec![T::zero(); m];
201        for i in 0..n {
202            let mut j = 0usize;
203            while j <= m && c[i][j].is_zero() {
204                j += 1;
205            }
206            if j == m {
207                return None;
208            }
209            if j < m {
210                x[j] = c[i][m];
211            }
212        }
213        Some(x)
214    }
215    pub fn inverse(&self) -> Option<Matrix<T>> {
216        assert_eq!(self.shape.0, self.shape.1);
217        let n = self.shape.0;
218        let mut c = Matrix::<T>::zeros((n, n * 2));
219        for i in 0..n {
220            c[i][..n].clone_from_slice(&self[i]);
221            c[i][n + i] = T::one();
222        }
223        c.row_reduction(true);
224        if (0..n).any(|i| c[i][i].is_zero()) {
225            None
226        } else {
227            Some(Self::from_vec(
228                c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
229            ))
230        }
231    }
Source§

impl<T> Matrix<T>
where T: Clone + Zero + One,

Source

pub fn eye(shape: (usize, usize)) -> Self

Examples found in repository?
crates/competitive/src/math/matrix.rs (line 128)
125    pub fn pow(&self, mut n: usize) -> Self {
126        assert_eq!(self.shape.0, self.shape.1);
127        let mut x = self.clone();
128        let mut res = Matrix::eye(self.shape);
129        while n > 0 {
130            if n & 1 == 1 {
131                res = &res * &x;
132            }
133            x = &x * &x;
134            n >>= 1;
135        }
136        res
137    }
Source§

impl<T> Matrix<T>
where T: Copy + Zero + One + Add<Output = T> + Mul<Output = T>,

Source

pub fn pow(&self, n: usize) -> Self

Source§

impl<T> Matrix<T>
where T: Copy + PartialEq + Zero + One + Sub<Output = T> + Mul<Output = T> + Div<Output = T>,

Source

pub fn row_reduction(&mut self, normalize: bool)

Examples found in repository?
crates/competitive/src/math/matrix.rs (line 177)
175    pub fn rank(&mut self) -> usize {
176        let n = self.shape.0;
177        self.row_reduction(false);
178        (0..n)
179            .filter(|&i| !self.data[i].iter().all(|x| x.is_zero()))
180            .count()
181    }
182    pub fn determinant(&mut self) -> T {
183        assert_eq!(self.shape.0, self.shape.1);
184        self.row_reduction(false);
185        let mut d = T::one();
186        for i in 0..self.shape.0 {
187            d = d * self[i][i];
188        }
189        d
190    }
191    pub fn solve_system_of_linear_equations(&self, b: &[T]) -> Option<Vec<T>> {
192        assert_eq!(self.shape.0, b.len());
193        let (n, m) = self.shape;
194        let mut c = Matrix::<T>::zeros((n, m + 1));
195        for i in 0..n {
196            c[i][..m].clone_from_slice(&self[i]);
197            c[i][m] = b[i];
198        }
199        c.row_reduction(true);
200        let mut x = vec![T::zero(); m];
201        for i in 0..n {
202            let mut j = 0usize;
203            while j <= m && c[i][j].is_zero() {
204                j += 1;
205            }
206            if j == m {
207                return None;
208            }
209            if j < m {
210                x[j] = c[i][m];
211            }
212        }
213        Some(x)
214    }
215    pub fn inverse(&self) -> Option<Matrix<T>> {
216        assert_eq!(self.shape.0, self.shape.1);
217        let n = self.shape.0;
218        let mut c = Matrix::<T>::zeros((n, n * 2));
219        for i in 0..n {
220            c[i][..n].clone_from_slice(&self[i]);
221            c[i][n + i] = T::one();
222        }
223        c.row_reduction(true);
224        if (0..n).any(|i| c[i][i].is_zero()) {
225            None
226        } else {
227            Some(Self::from_vec(
228                c.data.into_iter().map(|r| r[n..].to_vec()).collect(),
229            ))
230        }
231    }
Source

pub fn rank(&mut self) -> usize

Source

pub fn determinant(&mut self) -> T

Source

pub fn solve_system_of_linear_equations(&self, b: &[T]) -> Option<Vec<T>>

Examples found in repository?
crates/competitive/src/algorithm/esper.rs (line 76)
69    pub fn solve(self) -> EsperSolver<T, Input, Class, FC, FF> {
70        let data: HashMap<_, _> = self
71            .data
72            .into_iter()
73            .map(|(key, (a, b))| {
74                (
75                    key,
76                    Matrix::from_vec(a).solve_system_of_linear_equations(&b),
77                )
78            })
79            .collect();
80        EsperSolver {
81            class: self.class,
82            feature: self.feature,
83            data,
84            _marker: PhantomData,
85        }
86    }
87
88    pub fn solve_checked(self) -> EsperSolver<T, Input, Class, FC, FF>
89    where
90        Class: Debug,
91        T: Debug,
92    {
93        let data: HashMap<_, _> = self
94            .data
95            .into_iter()
96            .map(|(key, (a, b))| {
97                let mat = Matrix::from_vec(a);
98                let coeff = mat.solve_system_of_linear_equations(&b);
99                if coeff.is_none() {
100                    eprintln!(
101                        "failed to solve linear equations: key={:?} A={:?} b={:?}",
102                        key, &mat.data, &b
103                    );
104                }
105                (key, coeff)
106            })
107            .collect();
108        EsperSolver {
109            class: self.class,
110            feature: self.feature,
111            data,
112            _marker: PhantomData,
113        }
114    }
Source

pub fn inverse(&self) -> Option<Matrix<T>>

Trait Implementations§

Source§

impl<T> Add for &Matrix<T>
where T: Copy + Zero + Add<Output = T>,

Source§

type Output = Matrix<T>

The resulting type after applying the + operator.
Source§

fn add(self, rhs: Self) -> Self::Output

Performs the + operation. Read more
Source§

impl<T: Clone> Clone for Matrix<T>

Source§

fn clone(&self) -> Matrix<T>

Returns a duplicate of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<T: Debug> Debug for Matrix<T>

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<T> Index<(usize, usize)> for Matrix<T>

Source§

type Output = T

The returned type after indexing.
Source§

fn index(&self, index: (usize, usize)) -> &Self::Output

Performs the indexing (container[index]) operation. Read more
Source§

impl<T> Index<usize> for Matrix<T>

Source§

type Output = Vec<T>

The returned type after indexing.
Source§

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation. Read more
Source§

impl<T> IndexMut<(usize, usize)> for Matrix<T>

Source§

fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation. Read more
Source§

impl<T> IndexMut<usize> for Matrix<T>

Source§

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation. Read more
Source§

impl<T> Mul for &Matrix<T>
where T: Copy + Zero + Add<Output = T> + Mul<Output = T>,

Source§

type Output = Matrix<T>

The resulting type after applying the * operator.
Source§

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation. Read more
Source§

impl<T: PartialEq> PartialEq for Matrix<T>

Source§

fn eq(&self, other: &Matrix<T>) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

impl<T> Sub for &Matrix<T>
where T: Copy + Zero + Sub<Output = T>,

Source§

type Output = Matrix<T>

The resulting type after applying the - operator.
Source§

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation. Read more
Source§

impl<T: Eq> Eq for Matrix<T>

Source§

impl<T> StructuralPartialEq for Matrix<T>

Auto Trait Implementations§

§

impl<T> Freeze for Matrix<T>

§

impl<T> RefUnwindSafe for Matrix<T>
where T: RefUnwindSafe,

§

impl<T> Send for Matrix<T>
where T: Send,

§

impl<T> Sync for Matrix<T>
where T: Sync,

§

impl<T> Unpin for Matrix<T>
where T: Unpin,

§

impl<T> UnwindSafe for Matrix<T>
where T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.