求排序嵌套列表以分组字符、最小化相邻变更的高效算法

问题核心 #

给定包含任意数量'A'/'B'/'C'的嵌套列表（子列表数量1-10，每个子列表长度1-10），允许：

1. 调整子列表的顺序
2. 调整每个子列表内部字符的顺序（字符不能移出原属子列表）
   目标是让扁平化后的列表相邻字符变更次数最少，即尽可能集中同类字符。

比如输入：

[["A"],["B", "A", "A"],["B", "C", "B"],["C", "A"]]

原始扁平化后变更次数为7次；最优排列后：

[["A"],["A", "A", "B"],["B", "B", "C"],["C", "A"]]

扁平化后仅变更3次。

为什么贪心算法效果差 #

贪心每次选择当前衔接成本最低的子列表，但这种短视决策可能导致后续子列表的衔接成本大幅上升，无法得到全局最优解。比如示例中，若贪心先选["B","A","A"]（开头B），后续衔接的子列表可能带来更多变更，远不如先选["A"]再衔接同开头的子列表更优。

高效解决方案：动态规划+状态压缩 #

这个问题本质是旅行商问题（TSP）的变种，可以通过状态压缩的动态规划来求解全局最优解，具体步骤如下：

1. 预处理每个子列表

对每个子列表，先统计其中A/B/C的数量，然后生成所有可能的「首尾字符组合」，以及对应的：

• 内部排序后的字符序列（将同字符集中排列，比如["B","A","A"]可排成["A","A","B"]（首A尾B）或["B","A","A"]（首B尾A））
• 内部变更次数（等于子列表中不同字符的种类数-1，比如包含A和B的子列表，内部变更次数固定为1）

2. 动态规划（DP）状态定义

定义状态dp[mask][last_char]，其中：

• mask：二进制位掩码，每一位表示对应子列表是否已被使用（比如mask=0b0011表示第0、1个子列表已使用）
• last_char：当前排列的最后一个字符（A/B/C）
• 状态值：到达该状态时的累计变更次数（内部变更次数总和 + 子列表间的衔接变更次数总和）

3. 状态初始化

遍历每个子列表i，以及它的所有首尾组合(start, end)：

• 初始掩码mask = 1 << i
• 初始累计次数 = 该子列表的内部变更次数（第一个子列表无前置衔接，无额外变更）
• 将dp[mask][end]设为该初始次数（若有多个组合得到同一状态，保留最小值）

4. 状态转移

遍历所有已存在的状态(mask, last_char)，再遍历所有未使用的子列表j（即mask的第j位为0）：

• 对子列表j的每个首尾组合(start_j, end_j)：
  • 衔接变更次数：若start_j == last_char则为0，否则为1
  • 新掩码new_mask = mask | (1 << j)
  • 新累计次数 = 当前状态次数 + 衔接变更次数 + 子列表j的内部变更次数
  • 如果新累计次数小于dp[new_mask][end_j]的当前值，则更新该状态

5. 回溯最优路径

当所有子列表都被使用（mask = (1 << n) - 1，n为子列表总数），找到dp[mask][*]中的最小值，然后回溯状态转移过程，得到：

• 子列表的最优排列顺序
• 每个子列表对应的首尾组合（从而确定内部排序方式）

复杂度分析 #

子列表数量最多为10时：

• 掩码总数：2^10 = 1024
• 每个掩码对应3种last_char状态，总状态数：1024 * 3 = 3072
• 每个状态最多遍历10个未使用子列表，每个子列表最多6种首尾组合
  总计算量约18万次，完全可以在瞬间完成，效率极高。

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