problemreductions/rules/
exactcoverby3sets_subsetproduct.rs

1//! Reduction from ExactCoverBy3Sets to SubsetProduct.
2//!
3//! Assign a distinct prime to each universe element. Each triple becomes the
4//! product of its three primes, and the target is the product of all universe
5//! primes. Unique factorization then makes exact covers correspond exactly to
6//! subsets whose product matches the target.
7
8use crate::models::formula::ksat::first_n_odd_primes;
9use crate::models::misc::SubsetProduct;
10use crate::models::set::ExactCoverBy3Sets;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use num_bigint::BigUint;
14use num_traits::One;
15
16#[derive(Debug, Clone)]
17pub struct ReductionX3CToSubsetProduct {
18    target: SubsetProduct,
19}
20
21impl ReductionResult for ReductionX3CToSubsetProduct {
22    type Source = ExactCoverBy3Sets;
23    type Target = SubsetProduct;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
30        target_solution.to_vec()
31    }
32}
33
34fn product_biguint<I>(values: I) -> BigUint
35where
36    I: IntoIterator<Item = u64>,
37{
38    values.into_iter().fold(BigUint::one(), |product, value| {
39        product * BigUint::from(value)
40    })
41}
42
43fn assigned_primes(universe_size: usize) -> Vec<u64> {
44    match universe_size {
45        0 => Vec::new(),
46        1 => vec![2],
47        _ => {
48            let mut primes = Vec::with_capacity(universe_size);
49            primes.push(2);
50            primes.extend(first_n_odd_primes(universe_size - 1));
51            primes
52        }
53    }
54}
55
56#[reduction(overhead = {
57    num_elements = "num_sets",
58})]
59impl ReduceTo<SubsetProduct> for ExactCoverBy3Sets {
60    type Result = ReductionX3CToSubsetProduct;
61
62    fn reduce_to(&self) -> Self::Result {
63        let primes = assigned_primes(self.universe_size());
64        let values = self
65            .sets()
66            .iter()
67            .map(|set| product_biguint(set.iter().map(|&element| primes[element])))
68            .collect();
69        let target = product_biguint(primes.iter().copied());
70
71        ReductionX3CToSubsetProduct {
72            target: SubsetProduct::new(values, target),
73        }
74    }
75}
76
77#[cfg(feature = "example-db")]
78pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
79    use crate::export::SolutionPair;
80
81    vec![crate::example_db::specs::RuleExampleSpec {
82        id: "exactcoverby3sets_to_subsetproduct",
83        build: || {
84            crate::example_db::specs::rule_example_with_witness::<_, SubsetProduct>(
85                ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4]]),
86                SolutionPair {
87                    source_config: vec![1, 1, 0],
88                    target_config: vec![1, 1, 0],
89                },
90            )
91        },
92    }]
93}
94
95#[cfg(test)]
96#[path = "../unit_tests/rules/exactcoverby3sets_subsetproduct.rs"]
97mod tests;
problemreductions/rules/exactcoverby3sets_subsetproduct.rs

problemreductions/rules/
exactcoverby3sets_subsetproduct.rs
