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>`). We therefore implement the rule in
12//! the witness-style form used by `partition_multiprocessorscheduling.rs`:
13//! the optimal target witness directly recovers the source YES/NO answer via
14//! `source.evaluate(extract_solution(target_witness))`.
15//!
16//! Solution extraction is the identity (group assignment in the target is the
17//! subset assignment in the source). Small inputs with `|A| < 2` use a
18//! sentinel target `SumOfSquaresPartition::new(vec![1, 1], 2)` because
19//! `SumOfSquaresPartition` requires `num_groups <= num_elements`. The
20//! singleton case is correctly classified as NO: a single positive element
21//! cannot be split into two equal-sum groups.
22
23use crate::models::misc::{Partition, SumOfSquaresPartition};
24use crate::reduction;
25use crate::rules::traits::{ReduceTo, ReductionResult};
26
27/// Result of reducing Partition to SumOfSquaresPartition.
28#[derive(Debug, Clone)]
29pub struct ReductionPartitionToSumOfSquaresPartition {
30    target: SumOfSquaresPartition,
31    /// Number of elements in the original Partition instance.
32    /// Used to return a correctly-sized NO witness when the sentinel path is
33    /// taken (i.e. `source_n < 2`).
34    source_n: usize,
35}
36
37impl ReductionResult for ReductionPartitionToSumOfSquaresPartition {
38    type Source = Partition;
39    type Target = SumOfSquaresPartition;
40
41    fn target_problem(&self) -> &Self::Target {
42        &self.target
43    }
44
45    /// Solution extraction: identity mapping in the normal case.
46    /// In the sentinel case (source has fewer than two elements) the target's
47    /// witness has a different length, so we return an all-zero source-sized
48    /// vector; `Partition::evaluate` then yields `Or(false)`, which is the
49    /// correct answer because a single positive element cannot be balanced.
50    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
51        if target_solution.len() == self.source_n {
52            target_solution.to_vec()
53        } else {
54            vec![0; self.source_n]
55        }
56    }
57}
58
59#[reduction(overhead = {
60    num_elements = "num_elements",
61    num_groups = "2",
62})]
63impl ReduceTo<SumOfSquaresPartition> for Partition {
64    type Result = ReductionPartitionToSumOfSquaresPartition;
65
66    fn reduce_to(&self) -> Self::Result {
67        let source_n = self.num_elements();
68
69        if source_n < 2 {
70            // Sentinel: SumOfSquaresPartition requires num_groups <= num_elements,
71            // so we cannot build a K=2 instance from a singleton. The singleton
72            // Partition is always NO (a single positive element cannot be
73            // partitioned into two equal-sum subsets).
74            return ReductionPartitionToSumOfSquaresPartition {
75                target: SumOfSquaresPartition::new(vec![1, 1], 2),
76                source_n,
77            };
78        }
79
80        // Sizes in Partition are `u64` (always positive). Canonical inputs in
81        // this repo fit comfortably in `i64`; we cast directly.
82        let sizes_i64: Vec<i64> = self
83            .sizes()
84            .iter()
85            .map(|&s| i64::try_from(s).expect("Partition size exceeds i64::MAX"))
86            .collect();
87
88        ReductionPartitionToSumOfSquaresPartition {
89            target: SumOfSquaresPartition::new(sizes_i64, 2),
90            source_n,
91        }
92    }
93}
94
95#[cfg(feature = "example-db")]
96pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
97    use crate::export::SolutionPair;
98
99    vec![crate::example_db::specs::RuleExampleSpec {
100        id: "partition_to_sumofsquarespartition",
101        build: || {
102            // sizes [3, 1, 1, 2, 2, 1], S = 10, balanced split sums to 5/5.
103            // Witness: {3, 2} (group 0) and {1, 1, 2, 1} (group 1) -> 5^2 + 5^2 = 50 = S^2 / 2.
104            crate::example_db::specs::rule_example_with_witness::<_, SumOfSquaresPartition>(
105                Partition::new(vec![3, 1, 1, 2, 2, 1]),
106                SolutionPair {
107                    source_config: vec![0, 1, 1, 0, 1, 1],
108                    target_config: vec![0, 1, 1, 0, 1, 1],
109                },
110            )
111        },
112    }]
113}
114
115#[cfg(test)]
116#[path = "../unit_tests/rules/partition_sumofsquarespartition.rs"]
117mod tests;
problemreductions/rules/partition_sumofsquarespartition.rs

problemreductions/rules/
partition_sumofsquarespartition.rs
