problemreductions/rules/
subsetsum_partition.rs

1//! Reduction from Subset Sum to Partition.
2
3use crate::models::misc::{Partition, SubsetSum};
4use crate::reduction;
5use crate::rules::traits::{ReduceTo, ReductionResult};
6use num_bigint::BigUint;
7use num_traits::ToPrimitive;
8use std::cmp::Ordering;
9
10#[derive(Debug, Clone, Copy, PartialEq, Eq)]
11enum PaddingRelation {
12    None,
13    SameSide,
14    OppositeSide,
15}
16
17/// Result of reducing SubsetSum to Partition.
18#[derive(Debug, Clone)]
19pub struct ReductionSubsetSumToPartition {
20    target: Partition,
21    source_len: usize,
22    padding_relation: PaddingRelation,
23}
24
25impl ReductionResult for ReductionSubsetSumToPartition {
26    type Source = SubsetSum;
27    type Target = Partition;
28
29    fn target_problem(&self) -> &Self::Target {
30        &self.target
31    }
32
33    fn extract_solution(
34        &self,
35        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
36    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
37        crate::rules::traits::validate_target_witness(
38            self.target_problem(),
39            target_solution,
40            |value| value.0,
41            "target witness does not satisfy the target problem",
42        )?;
43
44        Ok({
45            let source_bits = &target_solution[..self.source_len];
46
47            match self.padding_relation {
48                PaddingRelation::None => source_bits.to_vec(),
49                PaddingRelation::SameSide => {
50                    let padding_is_selected = target_solution[self.source_len];
51                    source_bits
52                        .iter()
53                        .map(|&bit| if padding_is_selected { bit } else { !bit })
54                        .collect()
55                }
56                PaddingRelation::OppositeSide => {
57                    let padding_is_selected = target_solution[self.source_len];
58                    source_bits
59                        .iter()
60                        .map(|&bit| if padding_is_selected { !bit } else { bit })
61                        .collect()
62                }
63            }
64        })
65    }
66}
67
68#[crate::aggregate_reduction(identity)]
69impl crate::rules::AggregateReductionResult for ReductionSubsetSumToPartition {}
70
71// The padding |sum(sizes) - 2*target| is below (n+2)*2^h <= 2^(h+n+1).
72#[reduction(
73    transform = upper_bound {
74        max_numeric_magnitude_bits = "max_numeric_magnitude_bits + num_elements + 1",
75        num_elements = "num_elements + 1",
76    },
77    unavailable = {
78        total_sum = "target sum is source_sum + abs(source_sum - 2*target); neither raw source_sum nor target is in the source schema, which accepts arbitrary-precision values; a scale-sensitive bound from magnitude bits requires a variable exponent unsupported by the exact evaluator",
79    })]
80impl ReduceTo<Partition> for SubsetSum {
81    type Result = ReductionSubsetSumToPartition;
82
83    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
84        let total: BigUint = self.sizes().iter().cloned().sum();
85        let double_target = self.target() * 2u32;
86        let relation = total.cmp(&double_target);
87        let padding_relation = match relation {
88            Ordering::Equal => PaddingRelation::None,
89            Ordering::Greater => PaddingRelation::SameSide,
90            Ordering::Less => PaddingRelation::OppositeSide,
91        };
92
93        let convert = |value: &BigUint| {
94            value.to_i64().ok_or_else(|| {
95                crate::rules::ReductionError::invalid_target::<SubsetSum, Partition>(
96                    "a source size or derived padding does not fit the Partition i64 domain",
97                )
98            })
99        };
100        let mut sizes: Vec<i64> = self.sizes().iter().map(convert).collect::<Result<_, _>>()?;
101        match relation {
102            Ordering::Equal => {}
103            Ordering::Greater => sizes.push(convert(&(total - double_target))?),
104            Ordering::Less => sizes.push(convert(&(double_target - total))?),
105        }
106
107        Ok(ReductionSubsetSumToPartition {
108            target: Partition::new(sizes).map_err(|error| {
109                crate::rules::ReductionError::construction::<SubsetSum, Partition>(error)
110            })?,
111            source_len: self.num_elements(),
112            padding_relation,
113        })
114    }
115}
116
117#[cfg(feature = "example-db")]
118pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
119    use crate::export::SolutionPair;
120
121    vec![crate::example_db::specs::RuleExampleSpec {
122        id: "subsetsum_to_partition",
123        build: || {
124            crate::example_db::specs::rule_example_with_witness::<_, Partition>(
125                SubsetSum::new(vec![1u32, 5, 6, 8], 11u32),
126                SolutionPair {
127                    source_config: serde_json::json!(vec![false, true, true, false]),
128                    target_config: serde_json::json!(vec![false, true, true, false, false]),
129                },
130            )
131        },
132    }]
133}
134
135#[cfg(test)]
136#[path = "../unit_tests/rules/subsetsum_partition.rs"]
137mod tests;
problemreductions/rules/subsetsum_partition.rs

problemreductions/rules/
subsetsum_partition.rs
