problemreductions/models/set/
two_dimensional_consecutive_sets.rs

1//! 2-Dimensional Consecutive Sets problem implementation.
2//!
3//! Given a finite alphabet Σ and a collection C of subsets of Σ, determine whether
4//! Σ can be partitioned into disjoint ordered groups X₁, ..., Xₖ such that each
5//! group has at most one element from each subset, and each subset's elements
6//! are spread across consecutive groups.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use serde::de::Error as _;
11use serde::{Deserialize, Serialize};
12use std::collections::HashSet;
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "TwoDimensionalConsecutiveSets",
17        display_name: "2-Dimensional Consecutive Sets",
18        aliases: &[],
19        dimensions: &[],
20        category: crate::registry::ProblemCategory::Set,
21        module_path: module_path!(),
22        description: "Determine if alphabet can be partitioned into ordered groups with intersection and consecutiveness constraints",
23        fields: &[
24            FieldInfo { name: "alphabet_size", type_name: "usize", description: "Size of the alphabet (elements are 0..alphabet_size-1)" },
25            FieldInfo { name: "subsets", type_name: "Vec<Vec<usize>>", description: "Collection of subsets of the alphabet" },
26        ],
27    }
28}
29
30/// 2-Dimensional Consecutive Sets problem.
31///
32/// Given a finite alphabet Σ = {0, 1, ..., n-1} and a collection C = {Σ₁, ..., Σₘ}
33/// of subsets of Σ, determine whether Σ can be partitioned into disjoint sets
34/// X₁, X₂, ..., Xₖ such that:
35/// 1. Each Xᵢ has at most one element in common with each Σⱼ (intersection constraint)
36/// 2. For each Σⱼ, its elements are spread across |Σⱼ| consecutive groups (consecutiveness)
37///
38/// This is NP-complete (Lipski, 1977) via transformation from Graph 3-Colorability.
39///
40/// # Example
41///
42/// ```
43/// use problemreductions::models::set::TwoDimensionalConsecutiveSets;
44/// use problemreductions::{Problem, BruteForce};
45///
46/// // Alphabet: {0,1,2,3,4,5}
47/// // Subsets: {0,1,2}, {3,4,5}, {1,3}, {2,4}, {0,5}
48/// let problem = TwoDimensionalConsecutiveSets::new(
49///     6,
50///     vec![vec![0, 1, 2], vec![3, 4, 5], vec![1, 3], vec![2, 4], vec![0, 5]],
51/// );
52///
53/// // Partition: X0={0}, X1={1,5}, X2={2,3}, X3={4}
54/// // config[i] = group index of symbol i
55/// assert!(problem.evaluate(&vec![0, 1, 2, 2, 3, 1]).unwrap());
56/// ```
57#[derive(Debug, Clone, Serialize)]
58pub struct TwoDimensionalConsecutiveSets {
59    /// Size of the alphabet (elements are 0..alphabet_size-1).
60    alphabet_size: usize,
61    /// Collection of subsets, each a sorted list of alphabet elements.
62    subsets: Vec<Vec<usize>>,
63}
64
65#[derive(Debug, Deserialize)]
66struct TwoDimensionalConsecutiveSetsUnchecked {
67    alphabet_size: usize,
68    subsets: Vec<Vec<usize>>,
69}
70
71fn validate(
72    alphabet_size: usize,
73    subsets: &[Vec<usize>],
74) -> Result<(), crate::registry::ConstructionError> {
75    if alphabet_size == 0 {
76        return Err("Alphabet size must be positive".to_string().into());
77    }
78
79    for (i, subset) in subsets.iter().enumerate() {
80        let mut seen = HashSet::new();
81        for &elem in subset {
82            if elem >= alphabet_size {
83                return Err(format!(
84                    "Subset {} contains element {} which is outside alphabet of size {}",
85                    i, elem, alphabet_size
86                )
87                .into());
88            }
89            if !seen.insert(elem) {
90                return Err(format!("Subset {} contains duplicate element {}", i, elem).into());
91            }
92        }
93    }
94
95    Ok(())
96}
97
98impl<'de> Deserialize<'de> for TwoDimensionalConsecutiveSets {
99    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
100    where
101        D: serde::Deserializer<'de>,
102    {
103        let unchecked = TwoDimensionalConsecutiveSetsUnchecked::deserialize(deserializer)?;
104        Self::try_new(unchecked.alphabet_size, unchecked.subsets).map_err(D::Error::custom)
105    }
106}
107
108impl TwoDimensionalConsecutiveSets {
109    /// Create a new 2-Dimensional Consecutive Sets instance, returning validation errors.
110    pub fn try_new(
111        alphabet_size: usize,
112        subsets: Vec<Vec<usize>>,
113    ) -> Result<Self, crate::registry::ConstructionError> {
114        validate(alphabet_size, &subsets)?;
115        let subsets = subsets
116            .into_iter()
117            .map(|mut s| {
118                s.sort();
119                s
120            })
121            .collect();
122        Ok(Self {
123            alphabet_size,
124            subsets,
125        })
126    }
127
128    /// Create a new 2-Dimensional Consecutive Sets instance.
129    ///
130    /// # Panics
131    ///
132    /// Panics if `alphabet_size` is 0, if any subset contains elements
133    /// outside the alphabet, or if any subset has duplicate elements.
134    pub fn new(alphabet_size: usize, subsets: Vec<Vec<usize>>) -> Self {
135        Self::try_new(alphabet_size, subsets).unwrap_or_else(|message| panic!("{message}"))
136    }
137
138    /// Get the alphabet size.
139    pub fn alphabet_size(&self) -> usize {
140        self.alphabet_size
141    }
142
143    /// Get the number of subsets.
144    pub fn num_subsets(&self) -> usize {
145        self.subsets.len()
146    }
147
148    /// Get the subsets.
149    pub fn subsets(&self) -> &[Vec<usize>] {
150        &self.subsets
151    }
152}
153
154impl Problem for TwoDimensionalConsecutiveSets {
155    const NAME: &'static str = "TwoDimensionalConsecutiveSets";
156    type Solution = Vec<usize>;
157    type Value = crate::types::Or;
158
159    crate::problem_parameters![
160        ("alphabet_size", alphabet_size),
161        ("num_subsets", num_subsets),
162    ];
163
164    fn evaluate(
165        &self,
166        config: &Self::Solution,
167    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
168        Ok({
169            crate::types::Or({
170                if config.len() != self.alphabet_size {
171                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
172                        "group assignment length does not match the alphabet".into(),
173                    ));
174                }
175                if config.iter().any(|&v| v >= self.alphabet_size) {
176                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
177                        "group assignment contains an out-of-range group".into(),
178                    ));
179                }
180
181                // Empty labels do not create gaps in the partition order, so compress used labels first.
182                let mut used = vec![false; self.alphabet_size];
183                for &group in config {
184                    used[group] = true;
185                }
186                let mut dense_labels = vec![0; self.alphabet_size];
187                let mut next_label = 0;
188                for (label, is_used) in used.into_iter().enumerate() {
189                    if is_used {
190                        dense_labels[label] = next_label;
191                        next_label += 1;
192                    }
193                }
194
195                for subset in &self.subsets {
196                    if subset.is_empty() {
197                        continue;
198                    }
199                    let groups: Vec<usize> =
200                        subset.iter().map(|&s| dense_labels[config[s]]).collect();
201
202                    // Intersection constraint: all group indices must be distinct
203                    let unique: HashSet<usize> = groups.iter().copied().collect();
204                    if unique.len() != subset.len() {
205                        return Ok(crate::types::Or(false));
206                    }
207
208                    // Consecutiveness: group indices must form a contiguous range
209                    let min_g = *unique.iter().min().unwrap();
210                    let max_g = *unique.iter().max().unwrap();
211                    if max_g - min_g + 1 != subset.len() {
212                        return Ok(crate::types::Or(false));
213                    }
214                }
215
216                true
217            })
218        })
219    }
220
221    fn variant() -> Vec<(&'static str, &'static str)> {
222        crate::variant_params![]
223    }
224}
225
226impl crate::solvers::BruteForceProblem for TwoDimensionalConsecutiveSets {
227    fn dimensions(&self) -> Vec<usize> {
228        vec![self.alphabet_size; self.alphabet_size]
229    }
230}
231
232crate::declare_variants! {
233    default TwoDimensionalConsecutiveSets => "alphabet_size^alphabet_size",
234}
235
236crate::register_brute_force! {
237    TwoDimensionalConsecutiveSets,
238}
239
240#[cfg(feature = "example-db")]
241pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
242    vec![crate::example_db::specs::ModelExampleSpec {
243        id: "two_dimensional_consecutive_sets",
244        instance: Box::new(TwoDimensionalConsecutiveSets::new(
245            6,
246            vec![
247                vec![0, 1, 2],
248                vec![3, 4, 5],
249                vec![1, 3],
250                vec![2, 4],
251                vec![0, 5],
252            ],
253        )),
254        optimal_config: serde_json::json!(vec![0, 1, 2, 2, 3, 1]),
255        optimal_value: serde_json::json!(true),
256    }]
257}
258
259#[cfg(test)]
260#[path = "../../unit_tests/models/set/two_dimensional_consecutive_sets.rs"]
261mod tests;
problemreductions/models/set/two_dimensional_consecutive_sets.rs

problemreductions/models/set/
two_dimensional_consecutive_sets.rs
