problemreductions/rules/
partition_sumofsquarespartition.rs

1//! Reduction from Partition to SumOfSquaresPartition.
2//!
3//! This is the Garey & Johnson SP19 textbook construction specialised to `K = 2`:
4//! among all 2-way partitions of `A` with total sum `S`, the sum of squared
5//! group sums `S_1^2 + S_2^2 = S^2 - 2 S_1 S_2` is minimised exactly when
6//! `S_1 = S_2 = S/2`, giving minimum `S^2/2`. Hence the source `Partition`
7//! instance is YES iff the optimal target witness is a balanced split, in
8//! which case `Partition::evaluate(extracted_witness) = Or(true)`.
9//!
10//! The target `SumOfSquaresPartition` model has no `J` bound field — it is a
11//! pure minimisation (`Value = Min<i64>`). The completed optimum maps to YES/NO
12//! by testing `2 * optimum == S^2`; only a balanced target witness is decoded.
13//!
14//! Solution extraction is the identity (group assignment in the target is the
15//! subset assignment in the source). Small inputs with `|A| < 2` use a
16//! sentinel target `SumOfSquaresPartition::new(vec![1, 1], 2)` because
17//! `SumOfSquaresPartition` requires `num_groups <= num_elements`. The
18//! singleton case is correctly classified as NO: a single positive element
19//! cannot be split into two equal-sum groups.
20
21use crate::models::misc::{Partition, SumOfSquaresPartition};
22use crate::reduction;
23use crate::rules::traits::{ReduceTo, ReductionResult};
24
25/// Result of reducing Partition to SumOfSquaresPartition.
26#[derive(Debug, Clone)]
27pub struct ReductionPartitionToSumOfSquaresPartition {
28    target: SumOfSquaresPartition,
29    /// Number of elements in the original Partition instance.
30    /// Distinguishes the singleton NO case from the two-group construction.
31    source_n: usize,
32    source_sum: i64,
33}
34
35impl ReductionResult for ReductionPartitionToSumOfSquaresPartition {
36    type Source = Partition;
37    type Target = SumOfSquaresPartition;
38
39    fn target_problem(&self) -> &Self::Target {
40        &self.target
41    }
42
43    /// Solution extraction preserves the source elements. The sentinel target
44    /// appends elements, so only the prefix corresponding to actual source
45    /// elements is mapped back.
46    fn extract_solution(
47        &self,
48        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
49    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
50        crate::rules::traits::validate_target_witness(
51            self.target_problem(),
52            target_solution,
53            |value| crate::rules::AggregateReductionResult::extract_value(self, value).0,
54            "target witness does not certify a YES answer for the source",
55        )?;
56        if target_solution.len() != self.target.num_elements() {
57            return Err(crate::rules::ExtractionError::invalid(format!(
58                "expected {} target group assignments, got {}",
59                self.target.num_elements(),
60                target_solution.len()
61            )));
62        }
63
64        Ok(target_solution[..self.source_n]
65            .iter()
66            .map(|&group| group == 1)
67            .collect())
68    }
69}
70
71#[crate::aggregate_reduction]
72impl crate::rules::AggregateReductionResult for ReductionPartitionToSumOfSquaresPartition {
73    type Source = Partition;
74    type Target = SumOfSquaresPartition;
75
76    fn target_problem(&self) -> &Self::Target {
77        &self.target
78    }
79
80    fn extract_value(&self, value: crate::types::Min<i64>) -> crate::types::Or {
81        crate::types::Or(
82            self.source_n >= 2
83                && value
84                    .0
85                    .is_some_and(|cost| 2 * i128::from(cost) == i128::from(self.source_sum).pow(2)),
86        )
87    }
88}
89
90#[reduction(
91    transform = exact {
92        num_elements = "num_elements",
93        num_groups = "2",
94    })]
95impl ReduceTo<SumOfSquaresPartition> for Partition {
96    type Result = ReductionPartitionToSumOfSquaresPartition;
97
98    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
99        let source_n = self.num_elements();
100
101        if source_n < 2 {
102            // Sentinel: SumOfSquaresPartition requires num_groups <= num_elements,
103            // so we cannot build a K=2 instance from a singleton. The singleton
104            // Partition is always NO (a single positive element cannot be
105            // partitioned into two equal-sum subsets).
106            return Ok(ReductionPartitionToSumOfSquaresPartition {
107                source_sum: self.total_sum(),
108                target: SumOfSquaresPartition::new(vec![1, 1], 2),
109                source_n,
110            });
111        }
112
113        Ok(ReductionPartitionToSumOfSquaresPartition {
114            source_sum: self.total_sum(),
115            target: SumOfSquaresPartition::new(self.sizes().to_vec(), 2),
116            source_n,
117        })
118    }
119}
120
121#[cfg(feature = "example-db")]
122pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
123    use crate::export::SolutionPair;
124
125    vec![crate::example_db::specs::RuleExampleSpec {
126        id: "partition_to_sumofsquarespartition",
127        build: || {
128            // sizes [3, 1, 1, 2, 2, 1], S = 10, balanced split sums to 5/5.
129            // Witness: {3, 2} (group 0) and {1, 1, 2, 1} (group 1) -> 5^2 + 5^2 = 50 = S^2 / 2.
130            crate::example_db::specs::rule_example_with_witness::<_, SumOfSquaresPartition>(
131                Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap(),
132                SolutionPair {
133                    source_config: serde_json::json!(vec![false, true, true, false, true, true]),
134                    target_config: serde_json::json!(vec![0, 1, 1, 0, 1, 1]),
135                },
136            )
137        },
138    }]
139}
140
141#[cfg(test)]
142#[path = "../unit_tests/rules/partition_sumofsquarespartition.rs"]
143mod tests;
problemreductions/rules/partition_sumofsquarespartition.rs

problemreductions/rules/
partition_sumofsquarespartition.rs
