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)]
58pub struct ShortestCommonSupersequence {
59    alphabet_size: usize,
60    strings: Vec<Vec<usize>>,
61    max_length: usize,
62}
63
64#[derive(Debug, Deserialize, crate::CreateSpec)]
65struct ShortestCommonSupersequenceCreateSpec {
66    /// Input strings; the alphabet and maximum length are inferred from them.
67    #[create(codec = "semicolon-separated")]
68    strings: Vec<Vec<usize>>,
69}
70
71impl TryFrom<ShortestCommonSupersequenceCreateSpec> for ShortestCommonSupersequence {
72    type Error = crate::registry::ConstructionError;
73
74    fn try_from(spec: ShortestCommonSupersequenceCreateSpec) -> Result<Self, Self::Error> {
75        if spec.strings.is_empty() {
76            return Err("must have at least one string".to_string().into());
77        }
78
79        let alphabet_size = spec
80            .strings
81            .iter()
82            .flatten()
83            .copied()
84            .max()
85            .map(|symbol| {
86                symbol
87                    .checked_add(1)
88                    .ok_or_else(|| "alphabet size overflows usize".to_string())
89            })
90            .transpose()?
91            .unwrap_or(0);
92        let max_length = spec.strings.iter().try_fold(0_usize, |total, string| {
93            total
94                .checked_add(string.len())
95                .ok_or_else(|| "maximum supersequence length overflows usize".to_string())
96        })?;
97
98        Ok(Self {
99            alphabet_size,
100            strings: spec.strings,
101            max_length,
102        })
103    }
104}
105
106impl ShortestCommonSupersequence {
107    /// Create a new ShortestCommonSupersequence instance.
108    ///
109    /// `max_length` is computed automatically as the sum of all input string
110    /// lengths (the worst-case supersequence with no overlap).
111    ///
112    /// # Panics
113    ///
114    /// Panics if `strings` is empty, or if `alphabet_size` is 0 and any input
115    /// string is non-empty.
116    pub fn new(alphabet_size: usize, strings: Vec<Vec<usize>>) -> Self {
117        assert!(!strings.is_empty(), "must have at least one string");
118        let max_length: usize = strings.iter().map(|s| s.len()).sum();
119        assert!(
120            alphabet_size > 0 || strings.iter().all(|s| s.is_empty()),
121            "alphabet_size must be > 0 when any input string is non-empty"
122        );
123        Self {
124            alphabet_size,
125            strings,
126            max_length,
127        }
128    }
129
130    /// Returns the alphabet size.
131    pub fn alphabet_size(&self) -> usize {
132        self.alphabet_size
133    }
134
135    /// Returns the input strings.
136    pub fn strings(&self) -> &[Vec<usize>] {
137        &self.strings
138    }
139
140    /// Returns the maximum possible supersequence length.
141    pub fn max_length(&self) -> usize {
142        self.max_length
143    }
144
145    /// Returns the number of input strings.
146    pub fn num_strings(&self) -> usize {
147        self.strings.len()
148    }
149
150    /// Returns the total length of all input strings.
151    pub fn total_length(&self) -> usize {
152        self.strings.iter().map(|s| s.len()).sum()
153    }
154}
155
156/// Check whether `needle` is a subsequence of `haystack` using greedy
157/// left-to-right matching.
158fn is_subsequence(needle: &[usize], haystack: &[usize]) -> bool {
159    let mut it = haystack.iter();
160    for &ch in needle {
161        loop {
162            match it.next() {
163                Some(&c) if c == ch => break,
164                Some(_) => continue,
165                None => return false,
166            }
167        }
168    }
169    true
170}
171
172impl Problem for ShortestCommonSupersequence {
173    const NAME: &'static str = "ShortestCommonSupersequence";
174    type Solution = Vec<Option<usize>>;
175    type Value = Min<i64>;
176
177    crate::problem_parameters![
178        ("alphabet_size", alphabet_size),
179        ("max_length", max_length),
180        ("total_length", total_length),
181    ];
182
183    fn variant() -> Vec<(&'static str, &'static str)> {
184        crate::variant_params![]
185    }
186
187    fn evaluate(
188        &self,
189        config: &Self::Solution,
190    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
191        if config.len() != self.max_length {
192            return Err(crate::traits::EvaluationError::InvalidConfiguration(
193                "supersequence representation length does not match the bound".into(),
194            ));
195        }
196        if config
197            .iter()
198            .any(|symbol| symbol.is_some_and(|value| value >= self.alphabet_size))
199        {
200            return Err(crate::traits::EvaluationError::InvalidConfiguration(
201                "supersequence contains an out-of-range symbol".into(),
202            ));
203        }
204        let config = config
205            .iter()
206            .map(|symbol| symbol.unwrap_or(self.alphabet_size))
207            .collect::<Vec<_>>();
208        Ok({
209            let pad = self.alphabet_size;
210
211            // Find effective length = index of first padding symbol
212            let effective_length = config
213                .iter()
214                .position(|&v| v == pad)
215                .unwrap_or(self.max_length);
216
217            // Verify all positions after first padding are also padding (no interleaved padding)
218            for &v in &config[effective_length..] {
219                if v != pad {
220                    return Ok(Min(None));
221                }
222            }
223
224            let prefix = &config[..effective_length];
225
226            // Check every input string is a subsequence of the prefix
227            if !self.strings.iter().all(|s| is_subsequence(s, prefix)) {
228                return Ok(Min(None));
229            }
230
231            Min(Some(i64::try_from(effective_length).map_err(|_| {
232                crate::traits::EvaluationError::IntegerOverflow(
233                    "converting supersequence length to i64".into(),
234                )
235            })?))
236        })
237    }
238}
239
240impl crate::solvers::BruteForceProblem for ShortestCommonSupersequence {
241    fn dimensions(&self) -> Vec<usize> {
242        vec![self.alphabet_size + 1; self.max_length]
243    }
244}
245
246crate::declare_variants! {
247    default ShortestCommonSupersequence => "(alphabet_size + 1) ^ max_length" create ShortestCommonSupersequenceCreateSpec,
248}
249
250crate::register_brute_force! {
251    ShortestCommonSupersequence decode |problem: &ShortestCommonSupersequence, indices: Vec<usize>| indices.into_iter().map(|value| (value != problem.alphabet_size()).then_some(value)).collect(),
252}
253
254#[cfg(feature = "example-db")]
255pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
256    // Alphabet {0, 1}, strings [0,1] and [1,0]
257    // max_length = 2 + 2 = 4, search space = 3^4 = 81
258    // Optimal SCS length = 3, e.g. [0,1,0] padded to [0,1,0,2]
259    vec![crate::example_db::specs::ModelExampleSpec {
260        id: "shortest_common_supersequence",
261        instance: Box::new(ShortestCommonSupersequence::new(
262            2,
263            vec![vec![0, 1], vec![1, 0]],
264        )),
265        optimal_config: serde_json::json!(vec![Some(0), Some(1), Some(0), None]),
266        optimal_value: serde_json::json!(3),
267    }]
268}
269
270#[cfg(test)]
271#[path = "../../unit_tests/models/misc/shortest_common_supersequence.rs"]
272mod tests;
problemreductions/models/misc/shortest_common_supersequence.rs

problemreductions/models/misc/
shortest_common_supersequence.rs
