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

problemreductions/models/misc/
grouping_by_swapping.rs
