problemreductions/models/misc/
shortest_common_supersequence.rs

1//! Shortest Common Supersequence problem implementation.
2//!
3//! Given a set of strings over an alphabet, find the shortest common
4//! supersequence. A string `w` is a supersequence of `s` if `s` is a
5//! subsequence of `w` (i.e., `s` can be obtained by deleting zero or more
6//! characters from `w`).
7//!
8//! The configuration uses a fixed-length representation of `max_length`
9//! optional symbols. `None` serves as padding/end marker, and the effective
10//! supersequence is the prefix before the first `None`. `max_length` equals
11//! the sum of all input string lengths (the worst case where no overlap
12//! exists). This problem is NP-hard (Maier, 1978).
13
14use crate::registry::{CreateSpec, ProblemSchemaEntry};
15use crate::traits::Problem;
16use crate::types::Min;
17use serde::{Deserialize, Serialize};
18
19inventory::submit! {
20    ProblemSchemaEntry {
21        name: "ShortestCommonSupersequence",
22        display_name: "Shortest Common Supersequence",
23        aliases: &["SCS"],
24        dimensions: &[],
25        category: crate::registry::ProblemCategory::Misc,
26        module_path: module_path!(),
27        description: "Find a shortest common supersequence for a set of strings",
28        fields: ShortestCommonSupersequenceCreateSpec::FIELDS,
29    }
30}
31
32/// The Shortest Common Supersequence problem.
33///
34/// Given an alphabet of size `k` and a set of strings over `{0, ..., k-1}`,
35/// find the shortest string `w` such that every input string is a subsequence
36/// of `w`.
37///
38/// # Representation
39///
40/// The configuration is a vector of length `max_length`, where each entry is
41/// either a symbol in `{0, ..., alphabet_size - 1}` or `None` as padding. The
42/// effective supersequence is the prefix of symbols before the first padding
43/// value. Padding must be contiguous at the end.
44///
45/// # Example
46///
47/// ```
48/// use problemreductions::models::misc::ShortestCommonSupersequence;
49/// use problemreductions::{Problem, BruteForce};
50///
51/// // Alphabet {0, 1}, strings [0,1] and [1,0]
52/// let problem = ShortestCommonSupersequence::new(2, vec![vec![0, 1], vec![1, 0]]);
53/// let solver = BruteForce::new();
54/// let solution = solver.solve(&problem).unwrap();
55/// assert!(solution.is_some());
56/// ```
57#[derive(Debug, Clone, Serialize, Deserialize)]
58#[serde(try_from = "ShortestCommonSupersequenceData")]
59pub struct ShortestCommonSupersequence {
60    alphabet_size: usize,
61    strings: Vec<Vec<usize>>,
62    max_length: usize,
63}
64
65#[derive(Deserialize)]
66struct ShortestCommonSupersequenceData {
67    alphabet_size: usize,
68    strings: Vec<Vec<usize>>,
69}
70
71impl TryFrom<ShortestCommonSupersequenceData> for ShortestCommonSupersequence {
72    type Error = crate::registry::ConstructionError;
73
74    fn try_from(data: ShortestCommonSupersequenceData) -> Result<Self, Self::Error> {
75        Self::try_new(data.alphabet_size, data.strings)
76    }
77}
78
79#[derive(Debug, Deserialize, crate::CreateSpec)]
80struct ShortestCommonSupersequenceCreateSpec {
81    /// Input strings; the alphabet and maximum length are inferred from them.
82    #[create(codec = "semicolon-separated")]
83    strings: Vec<Vec<usize>>,
84}
85
86impl TryFrom<ShortestCommonSupersequenceCreateSpec> for ShortestCommonSupersequence {
87    type Error = crate::registry::ConstructionError;
88
89    fn try_from(spec: ShortestCommonSupersequenceCreateSpec) -> Result<Self, Self::Error> {
90        let alphabet_size = spec
91            .strings
92            .iter()
93            .flatten()
94            .copied()
95            .max()
96            .map(|symbol| {
97                symbol
98                    .checked_add(1)
99                    .ok_or_else(|| "alphabet size overflows usize".to_string())
100            })
101            .transpose()?
102            .unwrap_or(0);
103        Self::try_new(alphabet_size, spec.strings)
104    }
105}
106
107impl ShortestCommonSupersequence {
108    /// Create a new ShortestCommonSupersequence instance.
109    ///
110    /// `max_length` is computed automatically as the sum of all input string
111    /// lengths (the worst-case supersequence with no overlap).
112    ///
113    /// # Panics
114    ///
115    /// Panics if `strings` is empty, or if `alphabet_size` is 0 and any input
116    /// string is non-empty.
117    pub fn new(alphabet_size: usize, strings: Vec<Vec<usize>>) -> Self {
118        Self::try_new(alphabet_size, strings).unwrap_or_else(|error| panic!("{error}"))
119    }
120
121    fn try_new(
122        alphabet_size: usize,
123        strings: Vec<Vec<usize>>,
124    ) -> Result<Self, crate::registry::ConstructionError> {
125        if strings.is_empty() {
126            return Err("must have at least one string".into());
127        }
128        let max_length = strings.iter().try_fold(0usize, |total, string| {
129            total
130                .checked_add(string.len())
131                .ok_or("maximum string length overflows usize")
132        })?;
133        if !(alphabet_size > 0 || strings.iter().all(|s| s.is_empty())) {
134            return Err("alphabet_size must be > 0 when any input string is non-empty".into());
135        }
136        Ok(Self {
137            alphabet_size,
138            strings,
139            max_length,
140        })
141    }
142
143    /// Returns the alphabet size.
144    pub fn alphabet_size(&self) -> usize {
145        self.alphabet_size
146    }
147
148    /// Returns the input strings.
149    pub fn strings(&self) -> &[Vec<usize>] {
150        &self.strings
151    }
152
153    /// Returns the maximum possible supersequence length.
154    pub fn max_length(&self) -> usize {
155        self.max_length
156    }
157
158    /// Returns the number of input strings.
159    pub fn num_strings(&self) -> usize {
160        self.strings.len()
161    }
162
163    /// Returns the total length of all input strings.
164    pub fn total_length(&self) -> usize {
165        self.strings.iter().map(|s| s.len()).sum()
166    }
167}
168
169/// Check whether `needle` is a subsequence of `haystack` using greedy
170/// left-to-right matching.
171fn is_subsequence(needle: &[usize], haystack: &[usize]) -> bool {
172    let mut it = haystack.iter();
173    for &ch in needle {
174        loop {
175            match it.next() {
176                Some(&c) if c == ch => break,
177                Some(_) => continue,
178                None => return false,
179            }
180        }
181    }
182    true
183}
184
185impl Problem for ShortestCommonSupersequence {
186    const NAME: &'static str = "ShortestCommonSupersequence";
187    type Solution = Vec<Option<usize>>;
188    type Value = Min<i64>;
189
190    crate::problem_parameters![
191        ("alphabet_size", alphabet_size),
192        ("max_length", max_length),
193        ("total_length", total_length),
194    ];
195
196    fn variant() -> Vec<(&'static str, &'static str)> {
197        crate::variant_params![]
198    }
199
200    fn evaluate(
201        &self,
202        config: &Self::Solution,
203    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
204        if config.len() != self.max_length {
205            return Err(crate::traits::EvaluationError::InvalidConfiguration(
206                "supersequence representation length does not match the bound".into(),
207            ));
208        }
209        if config
210            .iter()
211            .any(|symbol| symbol.is_some_and(|value| value >= self.alphabet_size))
212        {
213            return Err(crate::traits::EvaluationError::InvalidConfiguration(
214                "supersequence contains an out-of-range symbol".into(),
215            ));
216        }
217        let config = config
218            .iter()
219            .map(|symbol| symbol.unwrap_or(self.alphabet_size))
220            .collect::<Vec<_>>();
221        Ok({
222            let pad = self.alphabet_size;
223
224            // Find effective length = index of first padding symbol
225            let effective_length = config
226                .iter()
227                .position(|&v| v == pad)
228                .unwrap_or(self.max_length);
229
230            // Verify all positions after first padding are also padding (no interleaved padding)
231            for &v in &config[effective_length..] {
232                if v != pad {
233                    return Ok(Min(None));
234                }
235            }
236
237            let prefix = &config[..effective_length];
238
239            // Check every input string is a subsequence of the prefix
240            if !self.strings.iter().all(|s| is_subsequence(s, prefix)) {
241                return Ok(Min(None));
242            }
243
244            Min(Some(i64::try_from(effective_length).map_err(|_| {
245                crate::traits::EvaluationError::IntegerOverflow(
246                    "converting supersequence length to i64".into(),
247                )
248            })?))
249        })
250    }
251}
252
253impl crate::solvers::BruteForceProblem for ShortestCommonSupersequence {
254    fn dimensions(&self) -> Vec<usize> {
255        vec![self.alphabet_size + 1; self.max_length]
256    }
257}
258
259crate::declare_variants! {
260    default ShortestCommonSupersequence => "(alphabet_size + 1) ^ max_length" create ShortestCommonSupersequenceCreateSpec,
261}
262
263crate::register_brute_force! {
264    ShortestCommonSupersequence decode |problem: &ShortestCommonSupersequence, indices: Vec<usize>| indices.into_iter().map(|value| (value != problem.alphabet_size()).then_some(value)).collect(),
265}
266
267#[cfg(feature = "example-db")]
268pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
269    // Alphabet {0, 1}, strings [0,1] and [1,0]
270    // max_length = 2 + 2 = 4, search space = 3^4 = 81
271    // Optimal SCS length = 3, e.g. [0,1,0] padded to [0,1,0,2]
272    vec![crate::example_db::specs::ModelExampleSpec {
273        id: "shortest_common_supersequence",
274        instance: Box::new(ShortestCommonSupersequence::new(
275            2,
276            vec![vec![0, 1], vec![1, 0]],
277        )),
278        optimal_config: serde_json::json!(vec![Some(0), Some(1), Some(0), None]),
279        optimal_value: serde_json::json!(3),
280    }]
281}
282
283#[cfg(test)]
284#[path = "../../unit_tests/models/misc/shortest_common_supersequence.rs"]
285mod tests;
problemreductions/models/misc/shortest_common_supersequence.rs

problemreductions/models/misc/
shortest_common_supersequence.rs
