problemreductions/rules/
partition_subsetsum.rs

1//! Reduction from Partition to SubsetSum.
2//!
3//! Partition is the special case of SubsetSum where the target B equals half the
4//! total sum. This reduction copies the element sizes and sets B = S/2. If S is
5//! odd, a trivially infeasible SubsetSum instance is returned (sizes = [], target = 1).
6
7use crate::models::misc::{Partition, SubsetSum};
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use num_bigint::{BigUint, ToBigUint};
11
12/// Result of reducing Partition to SubsetSum.
13#[derive(Debug, Clone)]
14pub struct ReductionPartitionToSubsetSum {
15    target: SubsetSum,
16    /// Number of elements in the original Partition instance.
17    /// When the total sum is odd, the target has 0 elements but the source has n.
18    source_n: usize,
19}
20
21impl ReductionResult for ReductionPartitionToSubsetSum {
22    type Source = Partition;
23    type Target = SubsetSum;
24
25    fn target_problem(&self) -> &Self::Target {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_witness(
34            self.target_problem(),
35            target_solution,
36            |value| value.0,
37            "target witness does not satisfy the target problem",
38        )?;
39
40        if target_solution.len() != self.source_n {
41            return Err(crate::rules::ExtractionError::invalid(format!(
42                "expected {} subset-selection values, got {}",
43                self.source_n,
44                target_solution.len()
45            )));
46        }
47        Ok(target_solution.to_vec())
48    }
49}
50
51#[crate::aggregate_reduction(identity)]
52impl crate::rules::AggregateReductionResult for ReductionPartitionToSubsetSum {}
53
54// The target is half the sum, bounded by n*2^h; odd sums use the constant NO instance.
55#[reduction(
56    transform = upper_bound {
57        max_numeric_magnitude_bits = "max_numeric_magnitude_bits + num_elements",
58        num_elements = "num_elements",
59    })]
60impl ReduceTo<SubsetSum> for Partition {
61    type Result = ReductionPartitionToSubsetSum;
62
63    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
64        let total = self.total_sum();
65        let source_n = self.num_elements();
66
67        Ok(if total % 2 != 0 {
68            // Odd total sum: no balanced partition exists.
69            // Return a trivially infeasible SubsetSum: no elements, target = 1.
70            ReductionPartitionToSubsetSum {
71                target: SubsetSum::new_unchecked(vec![], BigUint::from(1u32)),
72                source_n,
73            }
74        } else {
75            let sizes: Vec<BigUint> = self
76                .sizes()
77                .iter()
78                .map(|&size| {
79                    size.to_biguint()
80                        .expect("validated nonnegative Partition size")
81                })
82                .collect();
83            let target_val = (total / 2)
84                .to_biguint()
85                .expect("validated nonnegative Partition total");
86            ReductionPartitionToSubsetSum {
87                target: SubsetSum::new_unchecked(sizes, target_val),
88                source_n,
89            }
90        })
91    }
92}
93
94#[cfg(feature = "example-db")]
95pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
96    use crate::export::SolutionPair;
97
98    vec![crate::example_db::specs::RuleExampleSpec {
99        id: "partition_to_subsetsum",
100        build: || {
101            crate::example_db::specs::rule_example_with_witness::<_, SubsetSum>(
102                Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap(),
103                SolutionPair {
104                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
105                    target_config: serde_json::json!(vec![true, false, false, true, false, false]),
106                },
107            )
108        },
109    }]
110}
111
112#[cfg(test)]
113#[path = "../unit_tests/rules/partition_subsetsum.rs"]
114mod tests;
problemreductions/rules/partition_subsetsum.rs

problemreductions/rules/
partition_subsetsum.rs
