problemreductions/models/misc/
numerical_3_dimensional_matching.rs

1//! Numerical 3-Dimensional Matching (N3DM) problem implementation.
2//!
3//! Given disjoint sets W, X, Y each with m elements, sizes s(a) ∈ Z⁺ for
4//! every element with B/4 < s(a) < B/2, and a bound B where the total sum
5//! equals mB.  Decide whether W ∪ X ∪ Y can be partitioned into m triples,
6//! each containing one element from W, X, and Y, with each triple summing
7//! to exactly B.
8
9use crate::registry::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry};
10use crate::traits::Problem;
11use crate::types::Or;
12use serde::de::Error as _;
13use serde::{Deserialize, Deserializer, Serialize};
14
15inventory::submit! {
16    ProblemSchemaEntry {
17        name: "Numerical3DimensionalMatching",
18        display_name: "Numerical 3-Dimensional Matching",
19        aliases: &["N3DM"],
20        dimensions: &[],
21        module_path: module_path!(),
22        description: "Partition W∪X∪Y into m triples (one from each set) each summing to B",
23        fields: &[
24            FieldInfo { name: "sizes_w", type_name: "Vec<u64>", description: "Positive integer sizes for each element of W" },
25            FieldInfo { name: "sizes_x", type_name: "Vec<u64>", description: "Positive integer sizes for each element of X" },
26            FieldInfo { name: "sizes_y", type_name: "Vec<u64>", description: "Positive integer sizes for each element of Y" },
27            FieldInfo { name: "bound", type_name: "u64", description: "Target sum B for each triple" },
28        ],
29    }
30}
31
32inventory::submit! {
33    ProblemSizeFieldEntry {
34        name: "Numerical3DimensionalMatching",
35        fields: &["num_groups", "bound"],
36    }
37}
38
39#[derive(Debug, Clone, Serialize)]
40pub struct Numerical3DimensionalMatching {
41    sizes_w: Vec<u64>,
42    sizes_x: Vec<u64>,
43    sizes_y: Vec<u64>,
44    bound: u64,
45}
46
47impl Numerical3DimensionalMatching {
48    fn validate_inputs(
49        sizes_w: &[u64],
50        sizes_x: &[u64],
51        sizes_y: &[u64],
52        bound: u64,
53    ) -> Result<(), String> {
54        let m = sizes_w.len();
55        if m == 0 {
56            return Err(
57                "Numerical3DimensionalMatching requires at least one element per set".to_string(),
58            );
59        }
60        if sizes_x.len() != m || sizes_y.len() != m {
61            return Err(
62                "Numerical3DimensionalMatching requires all three sets to have the same size"
63                    .to_string(),
64            );
65        }
66        if bound == 0 {
67            return Err("Numerical3DimensionalMatching requires a positive bound".to_string());
68        }
69
70        let bound128 = u128::from(bound);
71        for &size in sizes_w.iter().chain(sizes_x.iter()).chain(sizes_y.iter()) {
72            if size == 0 {
73                return Err("All sizes must be positive (> 0)".to_string());
74            }
75            let size128 = u128::from(size);
76            if !(4 * size128 > bound128 && 2 * size128 < bound128) {
77                return Err("Every size must lie strictly between B/4 and B/2".to_string());
78            }
79        }
80
81        let total_sum: u128 = sizes_w
82            .iter()
83            .chain(sizes_x.iter())
84            .chain(sizes_y.iter())
85            .map(|&s| u128::from(s))
86            .sum();
87        let expected_sum = bound128 * (m as u128);
88        if total_sum != expected_sum {
89            return Err("Total sum of all sizes must equal m * bound".to_string());
90        }
91        if total_sum > u128::from(u64::MAX) {
92            return Err("Total sum exceeds u64 range".to_string());
93        }
94
95        Ok(())
96    }
97
98    pub fn try_new(
99        sizes_w: Vec<u64>,
100        sizes_x: Vec<u64>,
101        sizes_y: Vec<u64>,
102        bound: u64,
103    ) -> Result<Self, String> {
104        Self::validate_inputs(&sizes_w, &sizes_x, &sizes_y, bound)?;
105        Ok(Self {
106            sizes_w,
107            sizes_x,
108            sizes_y,
109            bound,
110        })
111    }
112
113    /// Create a new Numerical 3-Dimensional Matching instance.
114    ///
115    /// # Panics
116    ///
117    /// Panics if the input violates the N3DM invariants.
118    pub fn new(sizes_w: Vec<u64>, sizes_x: Vec<u64>, sizes_y: Vec<u64>, bound: u64) -> Self {
119        Self::try_new(sizes_w, sizes_x, sizes_y, bound)
120            .unwrap_or_else(|message| panic!("{message}"))
121    }
122
123    pub fn sizes_w(&self) -> &[u64] {
124        &self.sizes_w
125    }
126
127    pub fn sizes_x(&self) -> &[u64] {
128        &self.sizes_x
129    }
130
131    pub fn sizes_y(&self) -> &[u64] {
132        &self.sizes_y
133    }
134
135    pub fn bound(&self) -> u64 {
136        self.bound
137    }
138
139    pub fn num_groups(&self) -> usize {
140        self.sizes_w.len()
141    }
142}
143
144#[derive(Deserialize)]
145struct Numerical3DimensionalMatchingData {
146    sizes_w: Vec<u64>,
147    sizes_x: Vec<u64>,
148    sizes_y: Vec<u64>,
149    bound: u64,
150}
151
152impl<'de> Deserialize<'de> for Numerical3DimensionalMatching {
153    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
154    where
155        D: Deserializer<'de>,
156    {
157        let data = Numerical3DimensionalMatchingData::deserialize(deserializer)?;
158        Self::try_new(data.sizes_w, data.sizes_x, data.sizes_y, data.bound)
159            .map_err(D::Error::custom)
160    }
161}
162
163impl Problem for Numerical3DimensionalMatching {
164    const NAME: &'static str = "Numerical3DimensionalMatching";
165    type Value = Or;
166
167    fn variant() -> Vec<(&'static str, &'static str)> {
168        crate::variant_params![]
169    }
170
171    fn dims(&self) -> Vec<usize> {
172        vec![self.num_groups(); 2 * self.num_groups()]
173    }
174
175    fn evaluate(&self, config: &[usize]) -> Or {
176        Or({
177            let m = self.num_groups();
178            if config.len() != 2 * m {
179                return Or(false);
180            }
181
182            // First m values: assignment of X-elements to W-elements (must be a permutation)
183            let x_perm = &config[..m];
184            // Second m values: assignment of Y-elements to W-elements (must be a permutation)
185            let y_perm = &config[m..];
186
187            // Check that both are valid permutations of 0..m
188            let mut x_used = vec![false; m];
189            let mut y_used = vec![false; m];
190
191            for i in 0..m {
192                if x_perm[i] >= m || y_perm[i] >= m {
193                    return Or(false);
194                }
195                if x_used[x_perm[i]] || y_used[y_perm[i]] {
196                    return Or(false);
197                }
198                x_used[x_perm[i]] = true;
199                y_used[y_perm[i]] = true;
200            }
201
202            // Check that each triple sums to B
203            let target = u128::from(self.bound);
204            (0..m).all(|i| {
205                let sum = u128::from(self.sizes_w[i])
206                    + u128::from(self.sizes_x[x_perm[i]])
207                    + u128::from(self.sizes_y[y_perm[i]]);
208                sum == target
209            })
210        })
211    }
212}
213
214crate::declare_variants! {
215    default Numerical3DimensionalMatching => "num_groups^(2 * num_groups)",
216}
217
218#[cfg(feature = "example-db")]
219pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
220    vec![crate::example_db::specs::ModelExampleSpec {
221        id: "numerical_3_dimensional_matching",
222        instance: Box::new(Numerical3DimensionalMatching::new(
223            vec![4, 5],
224            vec![4, 5],
225            vec![5, 7],
226            15,
227        )),
228        optimal_config: vec![0, 1, 1, 0],
229        optimal_value: serde_json::json!(true),
230    }]
231}
232
233#[cfg(test)]
234#[path = "../../unit_tests/models/misc/numerical_3_dimensional_matching.rs"]
235mod tests;
problemreductions/models/misc/numerical_3_dimensional_matching.rs

problemreductions/models/misc/
numerical_3_dimensional_matching.rs
