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    /// Smallest h >= 1 with every element size and the target sum strictly below 2^h.
92    pub fn max_numeric_magnitude_bits(&self) -> u64 {
93        crate::types::max_numeric_magnitude_bits(
94            self.sizes
95                .iter()
96                .copied()
97                .chain(std::iter::once(self.bound)),
98        )
99    }
100
101    /// Create a new 3-Partition instance.
102    ///
103    /// # Panics
104    ///
105    /// Panics if the input violates the classical 3-Partition invariants.
106    pub fn new(sizes: Vec<i64>, bound: i64) -> Self {
107        Self::try_new(sizes, bound).unwrap_or_else(|message| panic!("{message}"))
108    }
109
110    pub fn sizes(&self) -> &[i64] {
111        &self.sizes
112    }
113
114    pub fn bound(&self) -> i64 {
115        self.bound
116    }
117
118    pub fn num_elements(&self) -> usize {
119        self.sizes.len()
120    }
121
122    pub fn num_groups(&self) -> usize {
123        self.sizes.len() / 3
124    }
125
126    pub fn total_sum(&self) -> i64 {
127        self.sizes
128            .iter()
129            .copied()
130            .reduce(|acc, value| {
131                acc.checked_add(value)
132                    .expect("validated sum must fit in i64")
133            })
134            .unwrap_or(0)
135    }
136
137    fn group_counts_and_sums(
138        &self,
139        config: &[usize],
140    ) -> Result<Option<GroupCountsAndSums>, crate::traits::EvaluationError> {
141        if config.len() != self.num_elements() {
142            return Ok(None);
143        }
144
145        let mut counts = vec![0usize; self.num_groups()];
146        let mut sums = vec![0_i64; self.num_groups()];
147
148        for (index, &group) in config.iter().enumerate() {
149            if group >= self.num_groups() {
150                return Ok(None);
151            }
152            counts[group] += 1;
153            sums[group] = sums[group].checked_add(self.sizes[index]).ok_or_else(|| {
154                crate::traits::EvaluationError::IntegerOverflow(
155                    "summing three-partition group".into(),
156                )
157            })?;
158        }
159
160        Ok(Some((counts, sums)))
161    }
162}
163
164#[derive(Deserialize, crate::CreateSpec)]
165struct ThreePartitionCreateSpec {
166    /// Positive integer sizes for the elements to partition.
167    #[create(codec = "comma-separated")]
168    sizes: Vec<i64>,
169    /// Target sum for each triple.
170    bound: i64,
171}
172
173impl TryFrom<ThreePartitionCreateSpec> for ThreePartition {
174    type Error = crate::registry::ConstructionError;
175
176    fn try_from(spec: ThreePartitionCreateSpec) -> Result<Self, Self::Error> {
177        Self::try_new(spec.sizes, spec.bound)
178    }
179}
180
181impl<'de> Deserialize<'de> for ThreePartition {
182    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
183    where
184        D: Deserializer<'de>,
185    {
186        let spec = ThreePartitionCreateSpec::deserialize(deserializer)?;
187        Self::try_from(spec).map_err(D::Error::custom)
188    }
189}
190
191impl Problem for ThreePartition {
192    const NAME: &'static str = "ThreePartition";
193    type Solution = Vec<usize>;
194    type Value = Or;
195
196    crate::problem_parameters![
197        ("bound", bound),
198        ("max_numeric_magnitude_bits", max_numeric_magnitude_bits),
199        ("num_elements", num_elements),
200        ("num_groups", num_groups),
201    ];
202
203    fn variant() -> Vec<(&'static str, &'static str)> {
204        crate::variant_params![]
205    }
206
207    fn evaluate(&self, config: &Self::Solution) -> Result<Or, crate::traits::EvaluationError> {
208        if config.len() != self.num_elements() {
209            return Err(crate::traits::EvaluationError::InvalidConfiguration(
210                "group assignment length does not match the elements".into(),
211            ));
212        }
213        if config.iter().any(|&group| group >= self.num_groups()) {
214            return Err(crate::traits::EvaluationError::InvalidConfiguration(
215                "group assignment contains an out-of-range group".into(),
216            ));
217        }
218        Ok({
219            Or({
220                let Some((counts, sums)) = self.group_counts_and_sums(config)? else {
221                    return Ok(Or(false));
222                };
223
224                counts.into_iter().all(|count| count == 3)
225                    && sums.into_iter().all(|sum| sum == self.bound)
226            })
227        })
228    }
229}
230
231impl crate::solvers::BruteForceProblem for ThreePartition {
232    fn dimensions(&self) -> Vec<usize> {
233        vec![self.num_groups(); self.num_elements()]
234    }
235}
236
237crate::declare_variants! {
238    default ThreePartition => "3^num_elements" create ThreePartitionCreateSpec,
239}
240
241crate::register_brute_force! {
242    ThreePartition,
243}
244
245#[cfg(feature = "example-db")]
246pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
247    vec![crate::example_db::specs::ModelExampleSpec {
248        id: "three_partition",
249        instance: Box::new(ThreePartition::new(vec![4, 5, 6, 4, 6, 5], 15)),
250        optimal_config: serde_json::json!(vec![0, 0, 0, 1, 1, 1]),
251        optimal_value: serde_json::json!(true),
252    }]
253}
254
255#[cfg(test)]
256#[path = "../../unit_tests/models/misc/three_partition.rs"]
257mod tests;
problemreductions/models/misc/three_partition.rs

problemreductions/models/misc/
three_partition.rs
