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

problemreductions/models/misc/
longest_common_subsequence.rs
