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::{FieldInfo, 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        module_path: module_path!(),
18        description: "Group equal symbols into contiguous blocks using at most K adjacent swaps",
19        fields: &[
20            FieldInfo { name: "alphabet_size", type_name: "usize", description: "Size of the alphabet" },
21            FieldInfo { name: "string", type_name: "Vec<usize>", description: "Input string over {0, ..., alphabet_size-1}" },
22            FieldInfo { name: "budget", type_name: "usize", description: "Maximum number of adjacent swaps allowed" },
23        ],
24    }
25}
26
27/// Grouping by Swapping.
28///
29/// A configuration is a length-`budget` swap program. Each entry is either an
30/// adjacent swap position `i` (swap positions `i` and `i + 1`) or the special
31/// no-op value `string_len - 1`.
32#[derive(Debug, Clone, Serialize, Deserialize)]
33pub struct GroupingBySwapping {
34    alphabet_size: usize,
35    string: Vec<usize>,
36    budget: usize,
37}
38
39impl GroupingBySwapping {
40    /// Create a new GroupingBySwapping instance.
41    ///
42    /// # Panics
43    ///
44    /// Panics if the string contains a symbol outside the declared alphabet,
45    /// or if the string is empty while the budget is positive.
46    pub fn new(alphabet_size: usize, string: Vec<usize>, budget: usize) -> Self {
47        assert!(
48            alphabet_size > 0 || string.is_empty(),
49            "alphabet_size must be > 0 when string is non-empty"
50        );
51        assert!(
52            string.iter().all(|&symbol| symbol < alphabet_size),
53            "input symbols must be less than alphabet_size"
54        );
55        assert!(
56            !string.is_empty() || budget == 0,
57            "budget must be 0 when string is empty"
58        );
59        Self {
60            alphabet_size,
61            string,
62            budget,
63        }
64    }
65
66    /// Returns the alphabet size.
67    pub fn alphabet_size(&self) -> usize {
68        self.alphabet_size
69    }
70
71    /// Returns the input string.
72    pub fn string(&self) -> &[usize] {
73        &self.string
74    }
75
76    /// Returns the swap budget.
77    pub fn budget(&self) -> usize {
78        self.budget
79    }
80
81    /// Returns the input string length.
82    pub fn string_len(&self) -> usize {
83        self.string.len()
84    }
85
86    /// Applies a swap program to the input string.
87    ///
88    /// Returns `None` if the configuration has the wrong length or contains an
89    /// out-of-range swap slot.
90    pub fn apply_swap_program(&self, config: &[usize]) -> Option<Vec<usize>> {
91        if config.len() != self.budget {
92            return None;
93        }
94        if self.string.is_empty() {
95            return if config.is_empty() {
96                Some(Vec::new())
97            } else {
98                None
99            };
100        }
101
102        let no_op = self.string.len() - 1;
103        let mut current = self.string.clone();
104        for &slot in config {
105            if slot >= self.string.len() {
106                return None;
107            }
108            if slot != no_op {
109                current.swap(slot, slot + 1);
110            }
111        }
112        Some(current)
113    }
114
115    /// Returns whether every symbol in `candidate` appears in a single block.
116    pub fn is_grouped(&self, candidate: &[usize]) -> bool {
117        if candidate.iter().any(|&symbol| symbol >= self.alphabet_size) {
118            return false;
119        }
120        if candidate.is_empty() {
121            return true;
122        }
123
124        let mut closed = vec![false; self.alphabet_size];
125        let mut current_symbol = candidate[0];
126
127        for &symbol in candidate.iter().skip(1) {
128            if symbol == current_symbol {
129                continue;
130            }
131            closed[current_symbol] = true;
132            if closed[symbol] {
133                return false;
134            }
135            current_symbol = symbol;
136        }
137
138        true
139    }
140}
141
142impl Problem for GroupingBySwapping {
143    const NAME: &'static str = "GroupingBySwapping";
144    type Value = crate::types::Or;
145
146    fn dims(&self) -> Vec<usize> {
147        vec![self.string_len(); self.budget]
148    }
149
150    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
151        crate::types::Or({
152            self.apply_swap_program(config)
153                .is_some_and(|candidate| self.is_grouped(&candidate))
154        })
155    }
156
157    fn variant() -> Vec<(&'static str, &'static str)> {
158        crate::variant_params![]
159    }
160}
161
162crate::declare_variants! {
163    default GroupingBySwapping => "string_len ^ budget",
164}
165
166#[cfg(feature = "example-db")]
167pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
168    vec![crate::example_db::specs::ModelExampleSpec {
169        id: "grouping_by_swapping",
170        instance: Box::new(GroupingBySwapping::new(3, vec![0, 1, 2, 0, 1, 2], 5)),
171        optimal_config: vec![2, 1, 3, 5, 5],
172        optimal_value: serde_json::json!(true),
173    }]
174}
175
176#[cfg(test)]
177#[path = "../../unit_tests/models/misc/grouping_by_swapping.rs"]
178mod tests;
problemreductions/models/misc/grouping_by_swapping.rs

problemreductions/models/misc/
grouping_by_swapping.rs
