如何在Java中合并多有序列表并保留各列表顺序，生成最短有效结果？

算力阿峰

2026-5-15

如何在Java中合并多个有序列表并生成最短的有效超序列？

问题背景

我手头有多个独立的有序列表，它们可能包含重复元素，也存在重叠的子序列。举个例子：

列表1: B,C,D
列表2: A,B,E
列表3: A,B,A,D
列表4: F,G

我需要把这些列表合并成一个有效超序列，满足两个核心要求：

每个原始列表的元素顺序必须严格保留——换句话说，原始列表必须能通过删除超序列中的某些元素得到（不能打乱原有顺序）。
优先选择最短的超序列（比如A,B,A,C,D,E,F,G就是优质结果，而直接拼接所有列表的B,C,D,A,B,E,A,B,A,D,F,G就过于冗长）。

需要注意，像A,B,C,D,E,F,G这种结果是无效的，因为第三个原始列表里B出现在A之后的顺序被破坏了，不符合要求。

解决方案：基于最短公共超序列（SCS）的实现

这个问题本质上是**多序列的最短公共超序列（Shortest Common Supersequence, SCS）**问题。核心思路是尽可能复用不同列表之间的公共子序列，同时严格保留每个列表的元素顺序。下面是Java的具体实现方案：

1. 先实现两个列表的最短公共超序列

我们先搞定两个列表的SCS生成，这是基础。用动态规划（DP）来计算并构造结果：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ShortestSupersequenceGenerator {

    // 生成两个列表的最短公共超序列
    public static <T> List<T> scsTwoLists(List<T> list1, List<T> list2) {
        int m = list1.size();
        int n = list2.size();
        
        // dp[i][j] 表示list1前i个元素和list2前j个元素的SCS长度
        int[][] dp = new int[m + 1][n + 1];

        // 边界初始化：其中一个列表为空时，SCS就是另一个列表的长度
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // 填充DP表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (list1.get(i - 1).equals(list2.get(j - 1))) {
                    // 元素相同，复用该元素，长度+1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 取两种选择的较小值：添加list1的元素 或 添加list2的元素
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        // 回溯构造SCS结果
        List<T> scs = new ArrayList<>();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (list1.get(i - 1).equals(list2.get(j - 1))) {
                scs.add(list1.get(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] < dp[i][j - 1]) {
                scs.add(list1.get(i - 1));
                i--;
            } else {
                scs.add(list2.get(j - 1));
                j--;
            }
        }

        // 处理剩余未加入的元素
        while (i > 0) {
            scs.add(list1.get(i - 1));
            i--;
        }
        while (j > 0) {
            scs.add(list2.get(j - 1));
            j--;
        }

        // 回溯是从后往前加的，反转得到正确顺序
        Collections.reverse(scs);
        return scs;
    }
}

2. 扩展到多个列表

有了两个列表的SCS方法，我们可以用贪心的方式迭代合并所有输入列表：每次把当前的结果和下一个列表合并，最终得到所有列表的最短公共超序列。

// 生成多个列表的最短公共超序列
    public static <T> List<T> scsMultipleLists(List<List<T>> inputLists) {
        if (inputLists == null || inputLists.isEmpty()) {
            return new ArrayList<>();
        }

        // 初始结果为第一个列表
        List<T> result = new ArrayList<>(inputLists.get(0));

        // 依次合并剩余列表
        for (int idx = 1; idx < inputLists.size(); idx++) {
            result = scsTwoLists(result, inputLists.get(idx));
        }

        return result;
    }

3. 测试示例

用你给出的输入测试一下：

public static void main(String[] args) {
        List<List<Character>> inputLists = new ArrayList<>();
        inputLists.add(List.of('B', 'C', 'D'));
        inputLists.add(List.of('A', 'B', 'E'));
        inputLists.add(List.of('A', 'B', 'A', 'D'));
        inputLists.add(List.of('F', 'G'));

        List<Character> shortestSupersequence = scsMultipleLists(inputLists);
        System.out.println("最短有效超序列：" + shortestSupersequence);
        // 输出示例：[A, B, A, C, D, E, F, G]（或其他等价的最短结果）
    }

关键说明

重复元素支持：代码用泛型和元素相等判断来处理重复元素，像A,B,A,D这种包含重复元素的列表也能正确处理。
贪心策略的局限性：逐步合并的方式是局部最优的贪心策略，在某些极端复杂的场景下可能得不到全局最短的超序列，但对于大多数实际场景（尤其是输入规模不大时），这个方案的结果已经足够优质，而且实现简单、效率较高。如果需要严格全局最优，需要更复杂的多序列DP，但时间复杂度会指数级上升（比如k个长度为n的列表，时间复杂度为O(n^k)），对于k较大的情况几乎不可行。
泛型兼容：代码已经做了泛型处理，可以支持任意可比较的元素类型（比如String、自定义对象等，只要正确实现了equals方法）。

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