haar_lib/linalg/mod_2/
gaussian_elim.rs

1//! ガウスの消去法 (mod 2)
2use crate::ds::bitset::*;
3
4/// mod 2上で行列を掃き出し、ランクを求める。
5pub fn gaussian_elim(mut a: Vec<Bitset>) -> (usize, Vec<Bitset>) {
6    let n = a.len();
7    let Some(m) = a.first().map(|a| a.len()) else {
8        return (0, a);
9    };
10
11    assert!(a.iter().all(|r| r.len() == m));
12    let mut rank = 0;
13
14    for j in 0..m {
15        let mut pivot = None;
16
17        for (i, ai) in a.iter().enumerate().skip(rank) {
18            if ai.test(j) {
19                pivot = Some(i);
20                break;
21            }
22        }
23
24        if let Some(pivot) = pivot {
25            a.swap(pivot, rank);
26
27            let ar = a.swap_remove(rank);
28
29            for ai in a.iter_mut() {
30                if ai.test(j) {
31                    ai.same_size_xor_assign(&ar);
32                }
33            }
34
35            a.push(ar);
36            a.swap(rank, n - 1);
37
38            rank += 1;
39        } else {
40            continue;
41        }
42    }
43
44    (rank, a)
45}
haar_lib/linalg/mod_2/gaussian_elim.rs

haar_lib/linalg/mod_2/
gaussian_elim.rs
