problemreductions/models/misc/
longest_common_subsequence.rs

1//! Longest Common Subsequence (LCS) problem implementation.
2//!
3//! Given a finite alphabet and a set of strings over that alphabet, find a
4//! longest common subsequence. The configuration is a fixed-length vector of
5//! `max_length` positions, where each entry is either a valid symbol or `None`
6//! as padding. Padding must be contiguous at the end.
7
8use crate::registry::{CreateSpec, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Max;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "LongestCommonSubsequence",
16        display_name: "Longest Common Subsequence",
17        aliases: &["LCS"],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Misc,
20        module_path: module_path!(),
21        description: "Find a longest common subsequence for a set of strings",
22        fields: LongestCommonSubsequenceCreateSpec::FIELDS,
23    }
24}
25
26/// The Longest Common Subsequence problem.
27///
28/// Given an alphabet of size `k` and a set of strings over `{0, ..., k-1}`,
29/// find a longest string `w` that is a subsequence of every input string.
30///
31/// # Representation
32///
33/// The configuration is a vector of length `max_length`, where each entry is
34/// either a symbol in `{0, ..., alphabet_size - 1}` or `None` as padding.
35/// Padding must be contiguous at the end of the vector. The effective
36/// subsequence consists of the symbols before padding starts. The objective is
37/// to maximize the effective length.
38#[derive(Debug, Clone, Serialize, Deserialize)]
39#[serde(try_from = "LongestCommonSubsequenceData")]
40pub struct LongestCommonSubsequence {
41    alphabet_size: usize,
42    strings: Vec<Vec<usize>>,
43    max_length: usize,
44}
45
46#[derive(Deserialize)]
47struct LongestCommonSubsequenceData {
48    alphabet_size: usize,
49    strings: Vec<Vec<usize>>,
50}
51
52impl TryFrom<LongestCommonSubsequenceData> for LongestCommonSubsequence {
53    type Error = crate::registry::ConstructionError;
54
55    fn try_from(data: LongestCommonSubsequenceData) -> Result<Self, Self::Error> {
56        Self::try_new(data.alphabet_size, data.strings)
57    }
58}
59
60#[derive(Debug, Deserialize, crate::CreateSpec)]
61struct LongestCommonSubsequenceCreateSpec {
62    /// Optional alphabet size; omitted values are inferred from the strings.
63    alphabet_size: Option<usize>,
64    /// Input strings over the shared alphabet.
65    #[create(codec = "character-rows")]
66    strings: Vec<Vec<usize>>,
67}
68
69impl TryFrom<LongestCommonSubsequenceCreateSpec> for LongestCommonSubsequence {
70    type Error = crate::registry::ConstructionError;
71
72    fn try_from(spec: LongestCommonSubsequenceCreateSpec) -> Result<Self, Self::Error> {
73        if !spec.strings.iter().any(|string| !string.is_empty()) {
74            return Err("at least one input string must be non-empty"
75                .to_string()
76                .into());
77        }
78        let inferred_alphabet_size = spec
79            .strings
80            .iter()
81            .flatten()
82            .copied()
83            .max()
84            .map(|symbol| {
85                symbol
86                    .checked_add(1)
87                    .ok_or_else(|| "inferred alphabet size overflows usize".to_string())
88            })
89            .transpose()?
90            .unwrap_or(0);
91        let alphabet_size = spec.alphabet_size.unwrap_or(inferred_alphabet_size);
92        Self::try_new(alphabet_size, spec.strings)
93    }
94}
95
96impl LongestCommonSubsequence {
97    /// Create a new LongestCommonSubsequence instance.
98    ///
99    /// The `max_length` is computed automatically as the minimum of all string
100    /// lengths (the maximum possible common subsequence length).
101    ///
102    /// # Panics
103    ///
104    /// Panics if `alphabet_size == 0` and any input string is non-empty, or if
105    /// an input symbol is outside the declared alphabet.
106    pub fn new(alphabet_size: usize, strings: Vec<Vec<usize>>) -> Self {
107        Self::try_new(alphabet_size, strings).unwrap_or_else(|error| panic!("{error}"))
108    }
109
110    fn try_new(
111        alphabet_size: usize,
112        strings: Vec<Vec<usize>>,
113    ) -> Result<Self, crate::registry::ConstructionError> {
114        let max_length = strings.iter().map(|s| s.len()).min().unwrap_or(0);
115        if !(alphabet_size > 0 || strings.iter().all(|s| s.is_empty())) {
116            return Err("alphabet_size must be > 0 when any input string is non-empty".into());
117        }
118        if !(strings
119            .iter()
120            .flat_map(|s| s.iter())
121            .all(|&symbol| symbol < alphabet_size))
122        {
123            return Err("input symbols must be less than alphabet_size".into());
124        }
125        Ok(Self {
126            alphabet_size,
127            strings,
128            max_length,
129        })
130    }
131
132    /// Returns the alphabet size.
133    pub fn alphabet_size(&self) -> usize {
134        self.alphabet_size
135    }
136
137    /// Returns the input strings.
138    pub fn strings(&self) -> &[Vec<usize>] {
139        &self.strings
140    }
141
142    /// Returns the `max_length` field.
143    pub fn max_length(&self) -> usize {
144        self.max_length
145    }
146
147    /// Returns the number of input strings.
148    pub fn num_strings(&self) -> usize {
149        self.strings.len()
150    }
151
152    /// Returns the total input length across all strings.
153    pub fn total_length(&self) -> usize {
154        self.strings.iter().map(|s| s.len()).sum()
155    }
156
157    /// Returns the sum of squared string lengths.
158    pub fn sum_squared_lengths(&self) -> usize {
159        self.strings.iter().map(|s| s.len() * s.len()).sum()
160    }
161
162    /// Returns the sum of triangular numbers len * (len + 1) / 2 across strings.
163    pub fn sum_triangular_lengths(&self) -> usize {
164        self.strings
165            .iter()
166            .map(|s| s.len() * (s.len() + 1) / 2)
167            .sum()
168    }
169
170    /// Returns the number of adjacent position transitions.
171    pub fn num_transitions(&self) -> usize {
172        self.max_length.saturating_sub(1)
173    }
174
175    /// Returns the cross-frequency product: the sum over each alphabet symbol
176    /// of the product of that symbol's frequency across all input strings.
177    ///
178    /// Formally: Σ_{c ∈ 0..alphabet_size} Π_{i=1..k} count(c, strings\[i\])
179    /// where count(c, s) is the number of occurrences of symbol c in string s.
180    ///
181    /// This equals the exact number of match-node vertices in the LCS → MaxIS
182    /// reduction graph.
183    pub fn cross_frequency_product(&self) -> usize {
184        (0..self.alphabet_size)
185            .map(|c| {
186                self.strings
187                    .iter()
188                    .map(|s| s.iter().filter(|&&sym| sym == c).count())
189                    .product::<usize>()
190            })
191            .sum()
192    }
193}
194
195/// Check whether `candidate` is a subsequence of `target` using greedy
196/// left-to-right matching.
197fn is_subsequence(candidate: &[usize], target: &[usize]) -> bool {
198    let mut it = target.iter();
199    for &symbol in candidate {
200        loop {
201            match it.next() {
202                Some(&next) if next == symbol => break,
203                Some(_) => continue,
204                None => return false,
205            }
206        }
207    }
208    true
209}
210
211impl Problem for LongestCommonSubsequence {
212    const NAME: &'static str = "LongestCommonSubsequence";
213    type Solution = Vec<Option<usize>>;
214    type Value = Max<i64>;
215
216    crate::problem_parameters![
217        ("alphabet_size", alphabet_size),
218        ("cross_frequency_product", cross_frequency_product),
219        ("max_length", max_length),
220        ("num_strings", num_strings),
221        ("num_transitions", num_transitions),
222        ("sum_triangular_lengths", sum_triangular_lengths),
223        ("total_length", total_length),
224    ];
225
226    fn variant() -> Vec<(&'static str, &'static str)> {
227        crate::variant_params![]
228    }
229
230    fn evaluate(
231        &self,
232        config: &Self::Solution,
233    ) -> Result<Max<i64>, crate::traits::EvaluationError> {
234        if config.len() != self.max_length {
235            return Err(crate::traits::EvaluationError::InvalidConfiguration(
236                "subsequence representation length does not match the bound".into(),
237            ));
238        }
239        if config
240            .iter()
241            .any(|symbol| symbol.is_some_and(|value| value >= self.alphabet_size))
242        {
243            return Err(crate::traits::EvaluationError::InvalidConfiguration(
244                "subsequence contains an out-of-range symbol".into(),
245            ));
246        }
247        let config = config
248            .iter()
249            .map(|symbol| symbol.unwrap_or(self.alphabet_size))
250            .collect::<Vec<_>>();
251        Ok({
252            let padding = self.alphabet_size;
253
254            // Find effective length = index of first padding symbol (or max_length if no padding).
255            let effective_length = config
256                .iter()
257                .position(|&s| s == padding)
258                .unwrap_or(self.max_length);
259
260            // Verify all positions after the first padding are also padding (no interleaved padding).
261            if config[effective_length..].iter().any(|&s| s != padding) {
262                return Ok(Max(None));
263            }
264
265            // Extract the non-padding prefix as the candidate subsequence.
266            let prefix = &config[..effective_length];
267
268            // Check the prefix is a subsequence of every input string.
269            if !self.strings.iter().all(|s| is_subsequence(prefix, s)) {
270                return Ok(Max(None));
271            }
272
273            Max(Some(i64::try_from(effective_length).map_err(|_| {
274                crate::traits::EvaluationError::IntegerOverflow(
275                    "converting subsequence length to i64".into(),
276                )
277            })?))
278        })
279    }
280}
281
282impl crate::solvers::BruteForceProblem for LongestCommonSubsequence {
283    fn dimensions(&self) -> Vec<usize> {
284        vec![self.alphabet_size + 1; self.max_length]
285    }
286}
287
288crate::declare_variants! {
289    default LongestCommonSubsequence => "(alphabet_size + 1) ^ max_length" create LongestCommonSubsequenceCreateSpec,
290}
291
292crate::register_brute_force! {
293    LongestCommonSubsequence decode |problem: &LongestCommonSubsequence, indices: Vec<usize>| indices.into_iter().map(|value| (value != problem.alphabet_size()).then_some(value)).collect(),
294}
295
296#[cfg(feature = "example-db")]
297pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
298    vec![crate::example_db::specs::ModelExampleSpec {
299        id: "longest_common_subsequence",
300        instance: Box::new(LongestCommonSubsequence::new(
301            2,
302            vec![
303                vec![0, 1, 0, 1, 1, 0],
304                vec![1, 0, 0, 1, 0, 1],
305                vec![0, 0, 1, 0, 1, 1],
306                vec![1, 1, 0, 0, 1, 0],
307                vec![0, 1, 0, 1, 0, 1],
308                vec![1, 0, 1, 0, 1, 0],
309            ],
310        )),
311        optimal_config: serde_json::json!(vec![Some(0), Some(0), Some(1), Some(0), None, None]),
312        optimal_value: serde_json::json!(4),
313    }]
314}
315
316#[cfg(test)]
317#[path = "../../unit_tests/models/misc/longest_common_subsequence.rs"]
318mod tests;
problemreductions/models/misc/longest_common_subsequence.rs

problemreductions/models/misc/
longest_common_subsequence.rs
