problemreductions/rules/
subsetsum_integerexpressionmembership.rs

1use crate::models::misc::SubsetSum;
2use crate::models::misc::{IntExpr, IntegerExpressionMembership};
3use crate::reduction;
4use crate::rules::traits::{ReduceTo, ReductionResult};
5use num_traits::ToPrimitive;
6
7#[derive(Debug, Clone)]
8pub struct ReductionSubsetSumToIntegerExpressionMembership {
9    target: IntegerExpressionMembership,
10}
11
12impl ReductionResult for ReductionSubsetSumToIntegerExpressionMembership {
13    type Source = SubsetSum;
14    type Target = IntegerExpressionMembership;
15
16    fn target_problem(&self) -> &Self::Target {
17        &self.target
18    }
19
20    fn extract_solution(
21        &self,
22        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
23    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
24        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
25
26        Ok({
27            // Union choice 0 = left = Atom(1) = exclude, choice 1 = right = Atom(s_i+1) = include.
28            // This maps directly to SubsetSum's 0/1 include/exclude encoding.
29            target_solution.to_vec()
30        })
31    }
32}
33
34/// Build a left-associative chain of `Sum` nodes over the given union nodes.
35///
36/// For n items with sizes s_0, ..., s_{n-1}, each item becomes
37/// `Union(Atom(1), Atom(s_i + 1))`. The chain is built as:
38/// `Sum(Sum(...Sum(Union_0, Union_1), Union_2), ..., Union_{n-1})`.
39///
40/// DFS order visits Union_0 first, then Union_1, etc., so config[i]
41/// corresponds to item i.
42fn build_expression(sizes: &[i64]) -> Result<IntExpr, &'static str> {
43    let make_union = |size: i64| -> Result<IntExpr, &'static str> {
44        let included = size
45            .checked_add(1)
46            .ok_or("an item size cannot be shifted into the target expression domain")?;
47        Ok(IntExpr::Union(
48            Box::new(IntExpr::Atom(1)),
49            Box::new(IntExpr::Atom(included)),
50        ))
51    };
52
53    let mut sizes = sizes.iter().copied();
54    let first = sizes
55        .next()
56        .ok_or("the target expression requires at least one source item")?;
57    let mut expr = make_union(first)?;
58    for size in sizes {
59        expr = IntExpr::Sum(Box::new(expr), Box::new(make_union(size)?));
60    }
61    Ok(expr)
62}
63
64#[reduction(
65    transform = exact {
66        num_union_nodes = "num_elements",
67    })]
68impl ReduceTo<IntegerExpressionMembership> for SubsetSum {
69    type Result = ReductionSubsetSumToIntegerExpressionMembership;
70
71    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
72        let sizes: Vec<i64> = self
73            .sizes()
74            .iter()
75            .map(|size| {
76                size.to_i64().ok_or_else(|| {
77                    crate::rules::ReductionError::invalid_target::<
78                        SubsetSum,
79                        IntegerExpressionMembership,
80                    >("subset size does not fit the target i64 domain")
81                })
82            })
83            .collect::<Result<_, _>>()?;
84
85        let shift =
86            i64::try_from(self.num_elements()).map_err(|_| {
87                crate::rules::ReductionError::integer_overflow::<
88                    SubsetSum,
89                    IntegerExpressionMembership,
90                >("converting the number of elements to i64")
91            })?;
92        let source_target = self.target().to_i64().ok_or_else(|| {
93            crate::rules::ReductionError::invalid_target::<SubsetSum, IntegerExpressionMembership>(
94                "subset target does not fit the target i64 domain",
95            )
96        })?;
97        let target =
98            source_target.checked_add(shift).ok_or_else(|| {
99                crate::rules::ReductionError::integer_overflow::<
100                    SubsetSum,
101                    IntegerExpressionMembership,
102                >("computing the shifted target")
103            })?;
104
105        let expr = build_expression(&sizes).map_err(|message| {
106            crate::rules::ReductionError::invalid_target::<SubsetSum, IntegerExpressionMembership>(
107                message,
108            )
109        })?;
110
111        Ok(ReductionSubsetSumToIntegerExpressionMembership {
112            target: IntegerExpressionMembership::new(expr, target),
113        })
114    }
115}
116
117#[cfg(feature = "example-db")]
118pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
119    use crate::export::SolutionPair;
120
121    vec![crate::example_db::specs::RuleExampleSpec {
122        id: "subsetsum_to_integerexpressionmembership",
123        build: || {
124            crate::example_db::specs::rule_example_with_witness::<_, IntegerExpressionMembership>(
125                SubsetSum::new(vec![1u32, 5, 6, 8], 11u32),
126                SolutionPair {
127                    source_config: serde_json::json!(vec![false, true, true, false]),
128                    target_config: serde_json::json!(vec![false, true, true, false]),
129                },
130            )
131        },
132    }]
133}
134
135#[cfg(test)]
136#[path = "../unit_tests/rules/subsetsum_integerexpressionmembership.rs"]
137mod tests;
problemreductions/rules/subsetsum_integerexpressionmembership.rs

problemreductions/rules/
subsetsum_integerexpressionmembership.rs
