problemreductions/models/misc/
grouping_by_swapping.rs

1//! Grouping by Swapping problem implementation.
2//!
3//! Given a string over a finite alphabet and a swap budget `K`, determine
4//! whether at most `K` adjacent swaps can transform the string so that every
5//! symbol appears in a single contiguous block.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "GroupingBySwapping",
14        display_name: "Grouping by Swapping",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Misc,
18        module_path: module_path!(),
19        description: "Group equal symbols into contiguous blocks using at most K adjacent swaps",
20        fields: GroupingBySwappingCreateSpec::FIELDS,
21    }
22}
23
24/// Grouping by Swapping.
25///
26/// A configuration is a length-`budget` swap program. Each entry is either an
27/// adjacent swap position `i` (swap positions `i` and `i + 1`) or the special
28/// no-op value `string_len - 1`.
29#[derive(Debug, Clone, Serialize, Deserialize)]
30#[serde(try_from = "GroupingBySwappingData")]
31pub struct GroupingBySwapping {
32    alphabet_size: usize,
33    string: Vec<usize>,
34    budget: usize,
35}
36
37#[derive(Deserialize)]
38struct GroupingBySwappingData {
39    alphabet_size: usize,
40    string: Vec<usize>,
41    budget: usize,
42}
43
44impl TryFrom<GroupingBySwappingData> for GroupingBySwapping {
45    type Error = crate::registry::ConstructionError;
46
47    fn try_from(data: GroupingBySwappingData) -> Result<Self, Self::Error> {
48        Self::try_new(data.alphabet_size, data.string, data.budget)
49    }
50}
51
52#[derive(Debug, Deserialize, crate::CreateSpec)]
53struct GroupingBySwappingCreateSpec {
54    /// Optional alphabet size; omitted values are inferred from the string.
55    alphabet_size: Option<usize>,
56    /// Input string to group.
57    #[create(codec = "comma-separated")]
58    string: Vec<usize>,
59    /// Maximum number of adjacent swaps.
60    bound: usize,
61}
62
63impl TryFrom<GroupingBySwappingCreateSpec> for GroupingBySwapping {
64    type Error = crate::registry::ConstructionError;
65
66    fn try_from(spec: GroupingBySwappingCreateSpec) -> Result<Self, Self::Error> {
67        let inferred_alphabet_size = spec
68            .string
69            .iter()
70            .copied()
71            .max()
72            .map(|symbol| {
73                symbol
74                    .checked_add(1)
75                    .ok_or_else(|| "inferred alphabet size overflows usize".to_string())
76            })
77            .transpose()?
78            .unwrap_or(0);
79        let alphabet_size = spec.alphabet_size.unwrap_or(inferred_alphabet_size);
80        Self::try_new(alphabet_size, spec.string, spec.bound)
81    }
82}
83
84impl GroupingBySwapping {
85    /// Create a new GroupingBySwapping instance.
86    ///
87    /// # Panics
88    ///
89    /// Panics if the string contains a symbol outside the declared alphabet,
90    /// or if the string is empty while the budget is positive.
91    pub fn new(alphabet_size: usize, string: Vec<usize>, budget: usize) -> Self {
92        Self::try_new(alphabet_size, string, budget).unwrap_or_else(|error| panic!("{error}"))
93    }
94
95    fn try_new(
96        alphabet_size: usize,
97        string: Vec<usize>,
98        budget: usize,
99    ) -> Result<Self, crate::registry::ConstructionError> {
100        if !(alphabet_size > 0 || string.is_empty()) {
101            return Err("alphabet_size must be > 0 when string is non-empty".into());
102        }
103        if !(string.iter().all(|&symbol| symbol < alphabet_size)) {
104            return Err("input symbols must be less than alphabet_size".into());
105        }
106        if string.is_empty() && budget != 0 {
107            return Err("budget must be 0 when string is empty".into());
108        }
109        Ok(Self {
110            alphabet_size,
111            string,
112            budget,
113        })
114    }
115
116    /// Returns the alphabet size.
117    pub fn alphabet_size(&self) -> usize {
118        self.alphabet_size
119    }
120
121    /// Returns the input string.
122    pub fn string(&self) -> &[usize] {
123        &self.string
124    }
125
126    /// Returns the swap budget.
127    pub fn budget(&self) -> usize {
128        self.budget
129    }
130
131    /// Returns the input string length.
132    pub fn string_len(&self) -> usize {
133        self.string.len()
134    }
135
136    /// Applies a swap program to the input string.
137    ///
138    /// Returns `None` if the configuration has the wrong length or contains an
139    /// out-of-range swap slot.
140    pub fn apply_swap_program(&self, config: &[usize]) -> Option<Vec<usize>> {
141        if config.len() != self.budget {
142            return None;
143        }
144        if self.string.is_empty() {
145            return if config.is_empty() {
146                Some(Vec::new())
147            } else {
148                None
149            };
150        }
151
152        let no_op = self.string.len() - 1;
153        let mut current = self.string.clone();
154        for &slot in config {
155            if slot >= self.string.len() {
156                return None;
157            }
158            if slot != no_op {
159                current.swap(slot, slot + 1);
160            }
161        }
162        Some(current)
163    }
164
165    /// Returns whether every symbol in `candidate` appears in a single block.
166    pub fn is_grouped(&self, candidate: &[usize]) -> bool {
167        if candidate.iter().any(|&symbol| symbol >= self.alphabet_size) {
168            return false;
169        }
170        if candidate.is_empty() {
171            return true;
172        }
173
174        let mut closed = vec![false; self.alphabet_size];
175        let mut current_symbol = candidate[0];
176
177        for &symbol in candidate.iter().skip(1) {
178            if symbol == current_symbol {
179                continue;
180            }
181            closed[current_symbol] = true;
182            if closed[symbol] {
183                return false;
184            }
185            current_symbol = symbol;
186        }
187
188        true
189    }
190}
191
192impl Problem for GroupingBySwapping {
193    const NAME: &'static str = "GroupingBySwapping";
194    type Solution = Vec<usize>;
195    type Value = crate::types::Or;
196
197    crate::problem_parameters![
198        ("alphabet_size", alphabet_size),
199        ("string_len", string_len),
200        ("budget", budget),
201    ];
202
203    fn evaluate(
204        &self,
205        config: &Self::Solution,
206    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
207        if config.len() != self.budget {
208            return Err(crate::traits::EvaluationError::InvalidConfiguration(
209                "swap-program length does not match the budget".into(),
210            ));
211        }
212        if config.iter().any(|&slot| slot >= self.string.len()) {
213            return Err(crate::traits::EvaluationError::InvalidConfiguration(
214                "swap program contains an out-of-range slot".into(),
215            ));
216        }
217        Ok({
218            crate::types::Or({
219                self.apply_swap_program(config)
220                    .is_some_and(|candidate| self.is_grouped(&candidate))
221            })
222        })
223    }
224
225    fn variant() -> Vec<(&'static str, &'static str)> {
226        crate::variant_params![]
227    }
228}
229
230impl crate::solvers::BruteForceProblem for GroupingBySwapping {
231    fn dimensions(&self) -> Vec<usize> {
232        vec![self.string_len(); self.budget]
233    }
234}
235
236crate::declare_variants! {
237    default GroupingBySwapping => "string_len ^ budget" create GroupingBySwappingCreateSpec,
238}
239
240crate::register_brute_force! {
241    GroupingBySwapping,
242}
243
244#[cfg(feature = "example-db")]
245pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
246    vec![crate::example_db::specs::ModelExampleSpec {
247        id: "grouping_by_swapping",
248        instance: Box::new(GroupingBySwapping::new(3, vec![0, 1, 2, 0, 1, 2], 5)),
249        optimal_config: serde_json::json!(vec![2, 1, 3, 5, 5]),
250        optimal_value: serde_json::json!(true),
251    }]
252}
253
254#[cfg(test)]
255#[path = "../../unit_tests/models/misc/grouping_by_swapping.rs"]
256mod tests;
problemreductions/models/misc/grouping_by_swapping.rs

problemreductions/models/misc/
grouping_by_swapping.rs
