problemreductions/rules/
exactcoverby3sets_algebraicequationsovergf2.rs

1//! Reduction from ExactCoverBy3Sets to AlgebraicEquationsOverGF2.
2
3use crate::models::algebraic::AlgebraicEquationsOverGF2;
4use crate::models::set::ExactCoverBy3Sets;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7
8#[derive(Debug, Clone)]
9pub struct ReductionX3CToAlgebraicEquationsOverGF2 {
10    target: AlgebraicEquationsOverGF2,
11}
12
13impl ReductionResult for ReductionX3CToAlgebraicEquationsOverGF2 {
14    type Source = ExactCoverBy3Sets;
15    type Target = AlgebraicEquationsOverGF2;
16
17    fn target_problem(&self) -> &Self::Target {
18        &self.target
19    }
20
21    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
22        target_solution.to_vec()
23    }
24}
25
26#[reduction(overhead = {
27    num_vars = "num_sets",
28})]
29impl ReduceTo<AlgebraicEquationsOverGF2> for ExactCoverBy3Sets {
30    type Result = ReductionX3CToAlgebraicEquationsOverGF2;
31
32    fn reduce_to(&self) -> Self::Result {
33        let mut sets_per_element = vec![Vec::new(); self.universe_size()];
34        for (set_index, set) in self.sets().iter().enumerate() {
35            for &element in set {
36                sets_per_element[element].push(set_index);
37            }
38        }
39
40        let mut equations = Vec::new();
41        for containing_sets in sets_per_element {
42            let mut linear_equation = containing_sets
43                .iter()
44                .map(|&set_index| vec![set_index])
45                .collect::<Vec<_>>();
46            linear_equation.push(vec![]);
47            equations.push(linear_equation);
48
49            for left in 0..containing_sets.len() {
50                for right in (left + 1)..containing_sets.len() {
51                    equations.push(vec![vec![containing_sets[left], containing_sets[right]]]);
52                }
53            }
54        }
55
56        ReductionX3CToAlgebraicEquationsOverGF2 {
57            target: AlgebraicEquationsOverGF2::new(self.num_sets(), equations)
58                .expect("reduction produces valid equations"),
59        }
60    }
61}
62
63#[cfg(feature = "example-db")]
64pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
65    use crate::export::SolutionPair;
66
67    vec![crate::example_db::specs::RuleExampleSpec {
68        id: "exactcoverby3sets_to_algebraicequationsovergf2",
69        build: || {
70            crate::example_db::specs::rule_example_with_witness::<_, AlgebraicEquationsOverGF2>(
71                ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4]]),
72                SolutionPair {
73                    source_config: vec![1, 1, 0],
74                    target_config: vec![1, 1, 0],
75                },
76            )
77        },
78    }]
79}
80
81#[cfg(test)]
82#[path = "../unit_tests/rules/exactcoverby3sets_algebraicequationsovergf2.rs"]
83mod tests;
problemreductions/rules/exactcoverby3sets_algebraicequationsovergf2.rs

problemreductions/rules/
exactcoverby3sets_algebraicequationsovergf2.rs
