problemreductions/rules/
exactcoverby3sets_maximumsetpacking.rs

1//! Reduction from ExactCoverBy3Sets to MaximumSetPacking.
2//!
3//! Given an X3C instance with universe X (|X| = 3q) and collection C of
4//! 3-element subsets, construct a `MaximumSetPacking<One>` instance where each
5//! triple becomes a variable-length set with unit weight. An exact cover
6//! of q disjoint triples corresponds to a maximum packing of value q.
7
8use crate::models::set::{ExactCoverBy3Sets, MaximumSetPacking};
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::types::One;
12
13/// Result of reducing ExactCoverBy3Sets to MaximumSetPacking<One>.
14#[derive(Debug, Clone)]
15pub struct ReductionXC3SToMaximumSetPacking {
16    target: MaximumSetPacking<One>,
17}
18
19impl ReductionResult for ReductionXC3SToMaximumSetPacking {
20    type Source = ExactCoverBy3Sets;
21    type Target = MaximumSetPacking<One>;
22
23    fn target_problem(&self) -> &MaximumSetPacking<One> {
24        &self.target
25    }
26
27    /// Extract X3C solution from MaximumSetPacking solution.
28    ///
29    /// The configuration is identity (same binary selection vector).
30    /// A packing of q disjoint 3-sets over a 3q-element universe is necessarily
31    /// an exact cover, so no additional checking is needed.
32    fn extract_solution(
33        &self,
34        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
35    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
36        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
37
38        Ok(target_solution.to_vec())
39    }
40}
41
42#[reduction(
43    transform = exact {
44        num_sets = "num_subsets",
45    },
46    unavailable = {
47        universe_size = "the exact target parameter is not represented by this reduction's symbolic transform",
48    }
49)]
50impl ReduceTo<MaximumSetPacking<One>> for ExactCoverBy3Sets {
51    type Result = ReductionXC3SToMaximumSetPacking;
52
53    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
54        let sets: Vec<Vec<usize>> = self
55            .subsets()
56            .iter()
57            .map(|triple| triple.to_vec())
58            .collect();
59
60        Ok(ReductionXC3SToMaximumSetPacking {
61            target: MaximumSetPacking::<One>::new(sets),
62        })
63    }
64}
65
66#[cfg(feature = "example-db")]
67pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
68    use crate::export::SolutionPair;
69
70    vec![crate::example_db::specs::RuleExampleSpec {
71        id: "exactcoverby3sets_to_maximumsetpacking",
72        build: || {
73            // Universe {0,1,2,3,4,5}, subsets [{0,1,2}, {0,1,3}, {3,4,5}, {2,4,5}, {1,3,5}]
74            // Exact cover: S0={0,1,2} + S2={3,4,5}
75            let source = ExactCoverBy3Sets::new(
76                6,
77                vec![[0, 1, 2], [0, 1, 3], [3, 4, 5], [2, 4, 5], [1, 3, 5]],
78            );
79            crate::example_db::specs::rule_example_with_witness::<_, MaximumSetPacking<One>>(
80                source,
81                SolutionPair {
82                    source_config: serde_json::json!(vec![true, false, true, false, false]),
83                    target_config: serde_json::json!(vec![true, false, true, false, false]),
84                },
85            )
86        },
87    }]
88}
89
90#[cfg(test)]
91#[path = "../unit_tests/rules/exactcoverby3sets_maximumsetpacking.rs"]
92mod tests;
problemreductions/rules/exactcoverby3sets_maximumsetpacking.rs

problemreductions/rules/
exactcoverby3sets_maximumsetpacking.rs
