[笔记] 序列变换问题

· 2026-04-21 ·

今晚打 AtCoder Weekday Contest 0010 Beta 的 E 题时遇到了之前没有遇到过的排列交换问题（其实这篇文章从动笔到发布拖了两个月...）。

和 Gemini 讨论一番后，总结一下此类序列变换问题。

排列变换

此类问题需要从给定的排列 $[p_1,p_2,\dots,p_n]$ 变换到排列 $[1,2,\dots,n]$ ，求最少的操作次数。但是允许的操作有区别。

这其实就是求插入排序的最小操作次数。每次操作其实相当于把一个数移出当前相对顺序，再放入到一个更合适的位置，并且其中已经排好序的不用动。

所以为了让操作数尽可能地少，我们要寻找尽可能多的且已经保持好相对顺序的数字，这恰好就是最长上升子序列的定义。

因此最终操作数就是 $n$ 减去最长上升子序列的长度。可以在 $O(n^2)$ 时间内解决，在利用二分优化的情况下可以 $O(n\log n)$ 解决。

很显然这是求冒泡排序的最少操作次数。由于每次我们只会交换 $a_{i}>a_{i+1}$ 的相邻对，每次交换会消除一个逆序对。最终有序状态的逆序对个数为 $0$ 。因此总操作次数就是原排列的逆序对个数。

求逆序对个数是一个经典的二维偏序问题，除了 $O(n^2)$ 的暴力解法，还有很多 $O(n\log n)$ 解法。

为了解决这个问题，我们需要切换到图论视角。将排列及其下标连有向边，不难发现其构成了若干个环。当我们交换两个数时：

假如计算得到原先的排列有 $k$ 个环，那么就可以进行 $n-k$ 次断环操作使其变成 $n$ 个自环（即排列 $[1,2,\dots,n]$ ）。

不难发现这是可以在不连环的情况下做到的，因此最少的操作次数就是 $n-k$ 。找环可以在遍历搜索环时标记已访问的元素，并在 $O(n)$ 时间内解决。

假如是两个排列互相变换呢？例如从排列 $[p_1,p_2,\dots,p_n]$ 变换到 $[q_1,q_2,\dots,q_n]$ ，最少操作次数如何计算？

一开始，我的想法是以排列 $[1,2,\dots,n]$ 为中介去变换排列 $[p_1,p_2,\dots,p_n]$ 和 $[q_1,q_2,\dots,q_n]$ ，将其化归为两个原问题之和，但是稍微构造容易发现不是最优解。

对于“允许交换排列中的任意两个数”的问题，我也想过计算两者的环数做差，但是很显然可能会有环数相同的两个不同排列，操作次数肯定不可能为 $0$ ，这个想法也被我枪毙了。

但其实处理方法很简单，可以直接杀死上面三个问题——换视角。

只需要把 $q$ 中每个数字重命名，使其成为顺序排列即可。例如 $p=[1,4,2,3],q=[3,2,4,1]$ ，我们把数字重命名：

\begin{aligned} 3\to1 \\ 2\to2 \\ 4\to3 \\ 1\to4 \\ \end{aligned}

那么排列就变成了 $p=[4,3,2,1],q=[1,2,3,4]$ ，由于重命名是不会影响结果的（毕竟我们只是改了个名字嘛），所以我们成功地化归到了之前的情况！

所以这个问题的关键在于，只有 $[1,2,\dots,n]$ 这个排列有 $n$ 个（自）环，这样才可以确保别的排列与它之间的变换的过程中与环个数对应。

更一般地说，假如我们考虑一般的的数组（可能带有重复数字），又会如何呢？

对于冒泡排序和插入排序，它们的核心逻辑是不变的（仍然是逆序对和最长不减子序列），我们主要考虑“允许交换排列中的任意两个数”时会发生什么。

同样进行连边操作，重复的数字重复连边。不难发现每个数字的入度和出度都是相等的（即整个图构成了一个欧拉图），并且其中每一个环就对应着原排列变换中的一个置换环。

操作次数最少时，这个图分解出的环要尽可能多，这个问题在图论中被称为最大欧拉环分解 (Maximum Eulerian Cycle Decomposition)。然而，这是一个 NP-Hard 的问题，在问题规模不大时，我们可以使用状态压缩动态规划解决。

读者可以在 Algorithms for the Maximum Eulerian Cycle Decomposition Problem 这篇论文中了解更多有关最大欧拉环分解的信息。