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;
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(&self, target_solution: &[usize]) -> Vec<usize> {
30        if target_solution.len() == self.source_n {
31            // Normal case: same elements, same binary vector.
32            target_solution.to_vec()
33        } else {
34            // Odd-sum case: target is trivially infeasible (0 elements).
35            // Return all-zero config for the source (which also won't satisfy it).
36            vec![0; self.source_n]
37        }
38    }
39}
40
41#[reduction(overhead = {
42    num_elements = "num_elements",
43})]
44impl ReduceTo<SubsetSum> for Partition {
45    type Result = ReductionPartitionToSubsetSum;
46
47    fn reduce_to(&self) -> Self::Result {
48        let total = self.total_sum();
49        let source_n = self.num_elements();
50
51        if !total.is_multiple_of(2) {
52            // Odd total sum: no balanced partition exists.
53            // Return a trivially infeasible SubsetSum: no elements, target = 1.
54            ReductionPartitionToSubsetSum {
55                target: SubsetSum::new_unchecked(vec![], BigUint::from(1u32)),
56                source_n,
57            }
58        } else {
59            let sizes: Vec<BigUint> = self.sizes().iter().map(|&s| BigUint::from(s)).collect();
60            let target_val = BigUint::from(total / 2);
61            ReductionPartitionToSubsetSum {
62                target: SubsetSum::new_unchecked(sizes, target_val),
63                source_n,
64            }
65        }
66    }
67}
68
69#[cfg(feature = "example-db")]
70pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
71    use crate::export::SolutionPair;
72
73    vec![crate::example_db::specs::RuleExampleSpec {
74        id: "partition_to_subsetsum",
75        build: || {
76            crate::example_db::specs::rule_example_with_witness::<_, SubsetSum>(
77                Partition::new(vec![3, 1, 1, 2, 2, 1]),
78                SolutionPair {
79                    source_config: vec![1, 0, 0, 1, 0, 0],
80                    target_config: vec![1, 0, 0, 1, 0, 0],
81                },
82            )
83        },
84    }]
85}
86
87#[cfg(test)]
88#[path = "../unit_tests/rules/partition_subsetsum.rs"]
89mod tests;
problemreductions/rules/partition_subsetsum.rs

problemreductions/rules/
partition_subsetsum.rs
