problemreductions/models/misc/
three_partition.rs

1//! 3-Partition problem implementation.
2//!
3//! Given 3m positive integers that each lie strictly between B/4 and B/2,
4//! determine whether they can be partitioned into m triples that all sum to B.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry};
7use crate::traits::Problem;
8use crate::types::Or;
9use serde::de::Error as _;
10use serde::{Deserialize, Deserializer, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "ThreePartition",
15        display_name: "3-Partition",
16        aliases: &["3Partition", "3-Partition"],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Partition 3m bounded positive integers into m triples whose sums all equal B",
21        fields: ThreePartitionCreateSpec::FIELDS,
22    }
23}
24
25#[derive(Debug, Clone, Serialize)]
26pub struct ThreePartition {
27    sizes: Vec<i64>,
28    bound: i64,
29}
30
31type GroupCountsAndSums = (Vec<usize>, Vec<i64>);
32
33impl ThreePartition {
34    fn validate_inputs(
35        sizes: &[i64],
36        bound: i64,
37    ) -> Result<(), crate::registry::ConstructionError> {
38        if sizes.is_empty() {
39            return Err("ThreePartition requires at least one element"
40                .to_string()
41                .into());
42        }
43        if !sizes.len().is_multiple_of(3) {
44            return Err(
45                "ThreePartition requires the number of elements to be a multiple of 3".into(),
46            );
47        }
48        if bound <= 0 {
49            return Err("ThreePartition requires a positive bound"
50                .to_string()
51                .into());
52        }
53        if sizes.iter().any(|&size| size <= 0) {
54            return Err("All sizes must be positive (> 0)".to_string().into());
55        }
56
57        for &size in sizes {
58            let four_times_size = i128::from(size) * 4;
59            let two_times_size = i128::from(size) * 2;
60            let bound = i128::from(bound);
61            if !(four_times_size > bound && two_times_size < bound) {
62                return Err("Every size must lie strictly between B/4 and B/2"
63                    .to_string()
64                    .into());
65            }
66        }
67
68        let total_sum = sizes
69            .iter()
70            .try_fold(0_i64, |total, &size| total.checked_add(size))
71            .ok_or("total size sum exceeds i64 range")?;
72        let group_count =
73            i64::try_from(sizes.len() / 3).map_err(|_| "group count exceeds i64 range")?;
74        let expected_sum = bound
75            .checked_mul(group_count)
76            .ok_or("group count times bound exceeds i64 range")?;
77        if total_sum != expected_sum {
78            return Err("Total sum of sizes must equal m * bound".to_string().into());
79        }
80        Ok(())
81    }
82
83    pub fn try_new(
84        sizes: Vec<i64>,
85        bound: i64,
86    ) -> Result<Self, crate::registry::ConstructionError> {
87        Self::validate_inputs(&sizes, bound)?;
88        Ok(Self { sizes, bound })
89    }
90
91    /// Create a new 3-Partition instance.
92    ///
93    /// # Panics
94    ///
95    /// Panics if the input violates the classical 3-Partition invariants.
96    pub fn new(sizes: Vec<i64>, bound: i64) -> Self {
97        Self::try_new(sizes, bound).unwrap_or_else(|message| panic!("{message}"))
98    }
99
100    pub fn sizes(&self) -> &[i64] {
101        &self.sizes
102    }
103
104    pub fn bound(&self) -> i64 {
105        self.bound
106    }
107
108    pub fn num_elements(&self) -> usize {
109        self.sizes.len()
110    }
111
112    pub fn num_groups(&self) -> usize {
113        self.sizes.len() / 3
114    }
115
116    pub fn total_sum(&self) -> i64 {
117        self.sizes
118            .iter()
119            .copied()
120            .reduce(|acc, value| {
121                acc.checked_add(value)
122                    .expect("validated sum must fit in i64")
123            })
124            .unwrap_or(0)
125    }
126
127    fn group_counts_and_sums(
128        &self,
129        config: &[usize],
130    ) -> Result<Option<GroupCountsAndSums>, crate::traits::EvaluationError> {
131        if config.len() != self.num_elements() {
132            return Ok(None);
133        }
134
135        let mut counts = vec![0usize; self.num_groups()];
136        let mut sums = vec![0_i64; self.num_groups()];
137
138        for (index, &group) in config.iter().enumerate() {
139            if group >= self.num_groups() {
140                return Ok(None);
141            }
142            counts[group] += 1;
143            sums[group] = sums[group].checked_add(self.sizes[index]).ok_or_else(|| {
144                crate::traits::EvaluationError::IntegerOverflow(
145                    "summing three-partition group".into(),
146                )
147            })?;
148        }
149
150        Ok(Some((counts, sums)))
151    }
152}
153
154#[derive(Deserialize, crate::CreateSpec)]
155struct ThreePartitionCreateSpec {
156    /// Positive integer sizes for the elements to partition.
157    #[create(codec = "comma-separated")]
158    sizes: Vec<i64>,
159    /// Target sum for each triple.
160    bound: i64,
161}
162
163impl TryFrom<ThreePartitionCreateSpec> for ThreePartition {
164    type Error = crate::registry::ConstructionError;
165
166    fn try_from(spec: ThreePartitionCreateSpec) -> Result<Self, Self::Error> {
167        Self::try_new(spec.sizes, spec.bound)
168    }
169}
170
171impl<'de> Deserialize<'de> for ThreePartition {
172    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
173    where
174        D: Deserializer<'de>,
175    {
176        let spec = ThreePartitionCreateSpec::deserialize(deserializer)?;
177        Self::try_from(spec).map_err(D::Error::custom)
178    }
179}
180
181impl Problem for ThreePartition {
182    const NAME: &'static str = "ThreePartition";
183    type Solution = Vec<usize>;
184    type Value = Or;
185
186    crate::problem_parameters![("num_elements", num_elements), ("num_groups", num_groups),];
187
188    fn variant() -> Vec<(&'static str, &'static str)> {
189        crate::variant_params![]
190    }
191
192    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
193        if config.len() != self.num_elements() {
194            return Err(crate::traits::EvaluationError::InvalidConfiguration(
195                "group assignment length does not match the elements".into(),
196            ));
197        }
198        if config.iter().any(|&group| group >= self.num_groups()) {
199            return Err(crate::traits::EvaluationError::InvalidConfiguration(
200                "group assignment contains an out-of-range group".into(),
201            ));
202        }
203        Ok({
204            Or({
205                let Some((counts, sums)) = self.group_counts_and_sums(config)? else {
206                    return Ok(Or(false));
207                };
208
209                counts.into_iter().all(|count| count == 3)
210                    && sums.into_iter().all(|sum| sum == self.bound)
211            })
212        })
213    }
214}
215
216impl crate::solvers::BruteForceProblem for ThreePartition {
217    fn dimensions(&self) -> Vec<usize> {
218        vec![self.num_groups(); self.num_elements()]
219    }
220}
221
222crate::declare_variants! {
223    default ThreePartition => "3^num_elements" create ThreePartitionCreateSpec,
224}
225
226crate::register_brute_force! {
227    ThreePartition,
228}
229
230#[cfg(feature = "example-db")]
231pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
232    vec![crate::example_db::specs::ModelExampleSpec {
233        id: "three_partition",
234        instance: Box::new(ThreePartition::new(vec![4, 5, 6, 4, 6, 5], 15)),
235        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
236        optimal_value: serde_json::json!(true),
237    }]
238}
239
240#[cfg(test)]
241#[path = "../../unit_tests/models/misc/three_partition.rs"]
242mod tests;
problemreductions/models/misc/three_partition.rs

problemreductions/models/misc/
three_partition.rs
