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_solution(self.target_problem(), target_solution)?;
34
35        if target_solution.len() != self.source_n {
36            return Err(crate::rules::ExtractionError::invalid(format!(
37                "expected {} subset-selection values, got {}",
38                self.source_n,
39                target_solution.len()
40            )));
41        }
42        Ok(target_solution.to_vec())
43    }
44}
45
46#[reduction(
47    transform = exact {
48        num_elements = "num_elements",
49    })]
50impl ReduceTo<SubsetSum> for Partition {
51    type Result = ReductionPartitionToSubsetSum;
52
53    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
54        let total = self.total_sum();
55        let source_n = self.num_elements();
56
57        Ok(if total % 2 != 0 {
58            // Odd total sum: no balanced partition exists.
59            // Return a trivially infeasible SubsetSum: no elements, target = 1.
60            ReductionPartitionToSubsetSum {
61                target: SubsetSum::new_unchecked(vec![], BigUint::from(1u32)),
62                source_n,
63            }
64        } else {
65            let sizes: Vec<BigUint> = self
66                .sizes()
67                .iter()
68                .map(|&size| {
69                    size.to_biguint()
70                        .expect("validated nonnegative Partition size")
71                })
72                .collect();
73            let target_val = (total / 2)
74                .to_biguint()
75                .expect("validated nonnegative Partition total");
76            ReductionPartitionToSubsetSum {
77                target: SubsetSum::new_unchecked(sizes, target_val),
78                source_n,
79            }
80        })
81    }
82}
83
84#[cfg(feature = "example-db")]
85pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
86    use crate::export::SolutionPair;
87
88    vec![crate::example_db::specs::RuleExampleSpec {
89        id: "partition_to_subsetsum",
90        build: || {
91            crate::example_db::specs::rule_example_with_witness::<_, SubsetSum>(
92                Partition::new(vec![3, 1, 1, 2, 2, 1]).unwrap(),
93                SolutionPair {
94                    source_config: serde_json::json!(vec![true, false, false, true, false, false]),
95                    target_config: serde_json::json!(vec![true, false, false, true, false, false]),
96                },
97            )
98        },
99    }]
100}
101
102#[cfg(test)]
103#[path = "../unit_tests/rules/partition_subsetsum.rs"]
104mod tests;
problemreductions/rules/partition_subsetsum.rs

problemreductions/rules/
partition_subsetsum.rs
