haar_lib/linalg/mod_2/
intersection_vector_space.rs

1//! $\mathbb{F}_2$ベクトル空間$u$と$v$の共通部分
2use crate::ds::bitset::*;
3use crate::linalg::mod_2::lineq::*;
4
5/// $\mathbb{F}_2$ベクトル空間$u$と$v$の共通部分の基底を求める。
6pub fn intersection_vector_space(u: Vec<Bitset>, v: Vec<Bitset>) -> Vec<Bitset> {
7    if u.is_empty() || v.is_empty() {
8        return vec![];
9    }
10
11    let n = u.len();
12    let m = v.len();
13
14    let dim = u[0].len();
15
16    let mut w = vec![Bitset::new(n + m); dim];
17    for (i, x) in u.iter().chain(v.iter()).enumerate() {
18        for (j, wj) in w.iter_mut().enumerate() {
19            if x.test(j) {
20                wj.flip(i);
21            }
22        }
23    }
24
25    let (_, s) = lineq(w, vec![false; dim]).unwrap();
26
27    let mut basis = vec![];
28    for x in s {
29        let mut b = Bitset::new(dim);
30        for (i, ui) in u.iter().enumerate() {
31            if x.test(i) {
32                b.same_size_xor_assign(ui);
33            }
34        }
35        basis.push(b);
36    }
37
38    basis
39}