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_solution(self.target_problem(), target_solution)?;
38
39        Ok({
40            let source_bits = &target_solution[..self.source_len];
41
42            match self.padding_relation {
43                PaddingRelation::None => source_bits.to_vec(),
44                PaddingRelation::SameSide => {
45                    let padding_is_selected = target_solution[self.source_len];
46                    source_bits
47                        .iter()
48                        .map(|&bit| if padding_is_selected { bit } else { !bit })
49                        .collect()
50                }
51                PaddingRelation::OppositeSide => {
52                    let padding_is_selected = target_solution[self.source_len];
53                    source_bits
54                        .iter()
55                        .map(|&bit| if padding_is_selected { !bit } else { bit })
56                        .collect()
57                }
58            }
59        })
60    }
61}
62
63#[reduction(
64    transform = exact {
65        num_elements = "num_elements + 1",
66    })]
67impl ReduceTo<Partition> for SubsetSum {
68    type Result = ReductionSubsetSumToPartition;
69
70    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
71        let total: BigUint = self.sizes().iter().cloned().sum();
72        let double_target = self.target() * 2u32;
73        let relation = total.cmp(&double_target);
74        let padding_relation = match relation {
75            Ordering::Equal => PaddingRelation::None,
76            Ordering::Greater => PaddingRelation::SameSide,
77            Ordering::Less => PaddingRelation::OppositeSide,
78        };
79
80        let convert = |value: &BigUint| {
81            value.to_i64().ok_or_else(|| {
82                crate::rules::ReductionError::invalid_target::<SubsetSum, Partition>(
83                    "a source size or derived padding does not fit the Partition i64 domain",
84                )
85            })
86        };
87        let mut sizes: Vec<i64> = self.sizes().iter().map(convert).collect::<Result<_, _>>()?;
88        match relation {
89            Ordering::Equal => {}
90            Ordering::Greater => sizes.push(convert(&(total - double_target))?),
91            Ordering::Less => sizes.push(convert(&(double_target - total))?),
92        }
93
94        Ok(ReductionSubsetSumToPartition {
95            target: Partition::new(sizes).map_err(|error| {
96                crate::rules::ReductionError::construction::<SubsetSum, Partition>(error)
97            })?,
98            source_len: self.num_elements(),
99            padding_relation,
100        })
101    }
102}
103
104#[cfg(feature = "example-db")]
105pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
106    use crate::export::SolutionPair;
107
108    vec![crate::example_db::specs::RuleExampleSpec {
109        id: "subsetsum_to_partition",
110        build: || {
111            crate::example_db::specs::rule_example_with_witness::<_, Partition>(
112                SubsetSum::new(vec![1u32, 5, 6, 8], 11u32),
113                SolutionPair {
114                    source_config: serde_json::json!(vec![false, true, true, false]),
115                    target_config: serde_json::json!(vec![false, true, true, false, false]),
116                },
117            )
118        },
119    }]
120}
121
122#[cfg(test)]
123#[path = "../unit_tests/rules/subsetsum_partition.rs"]
124mod tests;
problemreductions/rules/subsetsum_partition.rs

problemreductions/rules/
subsetsum_partition.rs
