保留相对索引顺序的多有序列表合并去重优化问题

算法名称 #

这个问题属于**多序列最小公共超序列（Minimum Common Supersequence, MCS）**问题，是双序列最小公共超序列问题的扩展场景。

通用表述 #

给定N个元素序列（每个序列内部仅保留原有先后顺序，并非排序后的序列），要求构造一个新序列，满足两个核心条件：

• 保序约束：每个输入序列都是新序列的子序列——即对任意输入序列中位置i<j的两个元素a、b，新序列中必须存在对应的位置p<q，使得新序列第p个元素为a、第q个元素为b。
• 最优性约束：新序列长度尽可能短（等价于尽可能去除重复元素，仅保留满足保序约束的必要重复）。

最优解决方案 #

复杂度说明 #

多序列的最小公共超序列问题属于NP-hard问题，不存在多项式时间的精确求解算法，需根据场景选择合适解法：

1. 双序列场景（N=2）：可通过动态规划（DP）精确求解

   • 状态定义：设dp[i][j]为第一个序列前i个元素与第二个序列前j个元素的最小公共超序列长度。
   • 状态转移：
     • 若两个序列当前元素相等（L1[i] = L2[j]），则dp[i][j] = dp[i-1][j-1] + 1；
     • 若不相等，则dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1。
   • 回溯DP表即可还原出具体的最小超序列。

2. 多序列场景（N>2）：

   • 贪心近似算法：每次选择当前所有未完成匹配的输入序列中，最靠前出现、能覆盖最多后续匹配需求的元素，逐步构建超序列。该方法实现简单，多数场景下效果较好，但无法保证全局最优。
   • 逐步合并法：先求解前两个序列的最小公共超序列，再将结果与第三个序列求解最小公共超序列，以此类推直到所有序列合并完成。结果依赖合并顺序，可能非全局最优，但实现成本低。
   • DAG最短路径建模：将每个元素的出现位置建模为有向无环图的节点，元素先后顺序对应有向边，将问题转化为寻找从起点到终点的最短路径，路径节点即为超序列元素。

结合示例来看：

• 示例1中，两个序列(a,b)和(b,a)的最小公共超序列长度为3，无法更短——任何长度为2的序列都无法同时满足两个输入序列的保序约束；
• 示例2中，(a,b,c)是最优解，因为它同时包含两个输入序列作为子序列，且长度最短。

内容的提问来源于stack exchange，提问作者Kratos