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(&self, target_solution: &[usize]) -> Vec<usize> {
34        let source_bits = &target_solution[..self.source_len];
35
36        match self.padding_relation {
37            PaddingRelation::None => source_bits.to_vec(),
38            PaddingRelation::SameSide => {
39                let padding_is_selected = target_solution[self.source_len] == 1;
40                source_bits
41                    .iter()
42                    .map(|&bit| if padding_is_selected { bit } else { 1 - bit })
43                    .collect()
44            }
45            PaddingRelation::OppositeSide => {
46                let padding_is_selected = target_solution[self.source_len] == 1;
47                source_bits
48                    .iter()
49                    .map(|&bit| if padding_is_selected { 1 - bit } else { bit })
50                    .collect()
51            }
52        }
53    }
54}
55
56fn biguint_to_u64(value: &BigUint) -> u64 {
57    value
58        .to_u64()
59        .expect("SubsetSum -> Partition requires all sizes and padding to fit in u64")
60}
61
62#[reduction(overhead = {
63    num_elements = "num_elements + 1",
64})]
65impl ReduceTo<Partition> for SubsetSum {
66    type Result = ReductionSubsetSumToPartition;
67
68    fn reduce_to(&self) -> Self::Result {
69        let total: BigUint = self.sizes().iter().cloned().sum();
70        let double_target = self.target() * 2u32;
71        let relation = total.cmp(&double_target);
72        let padding_relation = match relation {
73            Ordering::Equal => PaddingRelation::None,
74            Ordering::Greater => PaddingRelation::SameSide,
75            Ordering::Less => PaddingRelation::OppositeSide,
76        };
77
78        let mut sizes: Vec<u64> = self.sizes().iter().map(biguint_to_u64).collect();
79        match relation {
80            Ordering::Equal => {}
81            Ordering::Greater => sizes.push(biguint_to_u64(&(total - double_target))),
82            Ordering::Less => sizes.push(biguint_to_u64(&(double_target - total))),
83        }
84
85        ReductionSubsetSumToPartition {
86            target: Partition::new(sizes),
87            source_len: self.num_elements(),
88            padding_relation,
89        }
90    }
91}
92
93#[cfg(feature = "example-db")]
94pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
95    use crate::export::SolutionPair;
96
97    vec![crate::example_db::specs::RuleExampleSpec {
98        id: "subsetsum_to_partition",
99        build: || {
100            crate::example_db::specs::rule_example_with_witness::<_, Partition>(
101                SubsetSum::new(vec![1u32, 5, 6, 8], 11u32),
102                SolutionPair {
103                    source_config: vec![0, 1, 1, 0],
104                    target_config: vec![0, 1, 1, 0, 0],
105                },
106            )
107        },
108    }]
109}
110
111#[cfg(test)]
112#[path = "../unit_tests/rules/subsetsum_partition.rs"]
113mod tests;
problemreductions/rules/subsetsum_partition.rs

problemreductions/rules/
subsetsum_partition.rs
