交换问题

Published: June 28, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 01序列最少交换次数
• 置换排序最少交换次数
• 字符串转换最少交换次数

01序列最少交换次数

现在给定等长且含有相同数量1的两个二进制序列，记作A、B。

我们可以对序列A做如下操作，交换两个相邻的位的值。问最少需要多少次操作，可以将A转换为B。

譬如：

A=0110

B=1001

很显然将第一位和第二位交换，将第三位和第四位交换就可以得到想要的结果，且任意可能的方案都至少要进行两次交换，因此答案是2。

这个问题的解法非常简单，我们记A中1出现的位置从小到大为$a_1,a_2,\ldots,a_k$，B中1出现的位置从小到大为$b_1,b_2,\ldots,b_k$可以证明A中原本位于$a_i$的1会最终被放置在$b_i$。

事实上，我们永远不会交换两个相同的值，因此$a_{i+1}$永远不会交换到$a_1$之前。因此我们可以直接证明$a_1$与$b_1$相匹配（这里匹配的意思是A中原本$a_1$处的1最终会移动到$b_1$）。同理可以证明其它1的匹配。

因此答案为：$\sum_{i=1}^k|a_i-b_i|$

这个问题可以在树上进行定义。对于一颗树，我们为顶点的初始值赋值为1或0，接下来，每个顶点还有一个目标值。我们可以交换两个之间存在一条边的顶点的值，我们的目的是使得最终树上每个顶点的值和目标值相同，并要求步骤数最少。

很显然，如果目标值中的1和初始值中的1的数目不同（简单说目标值的和和初始值的和不同），那么问题是无解的。下面考虑相同的情况。

对于树中的任意一条边，该边会将树分成两个连通块。我们称连通块的不平衡度为连通块中值的和与目标值的和的差的绝对值。很显然删除边e后，两个连通块的不平衡度是相同的。记$f(e)$为树失去边e后形成的连通块的不平衡度，称为边两端不平衡度。 很显然式子 $\sum_{e\in E}f(e)$ 是结果的一个下界。我们可以这样理解这个式子，由于删除$e$后，两个连通块的不平衡度均为$f(e)$，那么必定至少有$f(e)$个1从一个连通块中经过边$e$转移到另外一个连通块中。

下面我们设计一个算法，可以在下界次操作中完成转换。

首先我们从图中删除所有两端不平衡度为0的边，仅保留不平衡度非0的边。假如连通块大小都为1，这意味着没有边存在，即所有顶点的值和目标值是相同的，这时候我们自然可以在下界次（0）操作中完成转换。

利用反证法，假设不存在这样的边e，使得e的两端顶点的值一个为1，一个为0，且为1的顶点所在连通块的值和减去目标值和是正数。任意考虑一个大小非1的连通块。连通块一定是树，因此一定存在度数为1的叶子结点$v$。叶子结点的值和目标值必定不同，我们不妨设叶子结点的值为0，目标值为1。之后考虑$v$的父结点$u$，很显然父结点一定也是0（否则与假设相悖）。利用归纳法我们可以推广证明对于任意高度的树，树中的值必定都是相同的。当然这样的话，就意味着连通块的不平衡度非0，这是不可能的。因此假设不成立，存在这样的一条边，两端顶点值不同且1所在的连通块的值减去目标值和是正数。

我们将上面提到的边两端的顶点的值交换，发现除了$e$两端不平衡度减少了1以外，其余边的不平衡度都没有发生变化。

而上面的操作最多发生下界次，因此就证明了存在一种方案可以在下界次交换中使得每个顶点的值和目标值是相同的。

置换排序最少交换次数

一道综合题目。

问题1：给定$1,2,\ldots,n$的置换序列$a_1,\ldots,a_n$，每一次操作是交换两个相邻的数，问最少需要多少次操作才能将序列排序。

记$x$为序列中的逆序对数目，可以发现我们每次交换都可以且最多仅可以将逆序对数目减少1，只有逆序对数目为$0$的情况下流程才结束。因此答案就是$x$。

要统计逆序对，可以利用BIT。时间复杂度为$O(n\log_2n)$。

问题2：给定$1,2,\ldots,n$的置换序列$a_1,\ldots,a_n$，每一次操作是交换两个不同位置的数，问最少需要多少次操作才能将序列排序。

在置换的角度来看，我们可以发现问题实际上在问我们可以用多少个二元置换将输入置换恢复为标准置换。我们从图的角度来看置换，这时候置换可以表示为若干个环，每个二元置换，如果发生在同一个环中，这个环会被拆分成两个环，如果发生在不同的环中，这两个环会被合并为一个环。而我们的目的是的到$n$个环，因此至少需要操作次数为$n-C$，其中$C$表示原来的环数。

问题3：给定$1,2,\ldots,n$的置换序列$a_1,\ldots,a_n$，每一次操作是删除一个数，并将被删除的数插入到任意位置，问最少需要多少次操作才能将序列排序。

可以发现没有被删除的数一定保留原来的顺序，换言之，它们是严格递增子序列，其余数需要一次删除。因此我们要让删除次数最少等价于不被删除的数最多，即求LIS，答案为$n-LIS$。

问题4：给定$1,2,\ldots,n$的置换序列$a_1,\ldots,a_n$，每一次操作是删除一个数，并将被删除的数插入序列最前面，问最少需要多少次操作才能将序列排序。

首先每个数最多被删除一次，如果数字$m$被删除，则$m-1$一定也会被删除一次。因此我们要让被删除的最大数最小，而其余不被删除的数保持原来顺序，因此我们要找到形如$i,i+1,\ldots,n$的最长递增子序列。这个可以$O(n)$求解。

问题5：给定$1,2,\ldots,n$的置换序列$a_1,\ldots,a_n$，每次操作选择任意个互不相交的下标对，之后对没对下标$(i,j)$，交换$a_i$和$a_j$。现在要求用最少的操作次数使得序列有序，给出最少操作次数。

提供一道题目。

首先如果置换已经有序，答案为$0$。否则如果对于所有$i$都有$i=a_{a_i}$成立，那么答案为$1$，我们直接将这些元素全部交换。否则，答案至少为$2$。下面我们给出一个算法可以在两次操作解决这个问题。

首先这时候一定至少有一个环长度大于$2$。设环的长度为$m$，且环中的元素为$c_1,\ldots,c_{m}$。对于任意$k\geq 0$，如果有$2+k\lt m-k$，则在第一轮交换$(2+k,m-k)$。在第一轮操作后，会发现一定有对于所有$i$都有$i=a_{a_i}$成立，这时候一次简单操作就可以使得整个序列有序。（理解一下二元置换意味着拆环，第一轮我们将环拆分成不超过$2$长度）。

问题6：给定$1,2,\ldots,n$的置换序列$a_1,\ldots,a_n$，每一次操作是删除一个数，并将被删除的数插入序列最前面或最后面，问最少需要多少次操作才能将序列排序。

如果一个数$x$被插入到前面，则$x-1$一定也要被操作一次。同理如果一个数$x$被插入到后面，则$x+1$一定也会被插入到后面一次。因此真正不动的是一段递增序列$a_1,\ldots,a_k$，其中$a_i=a_1+i-1$。

可以直接线性算法求解答案，结果为$O(n)$。

问题7：给定一个01序列，要求对其排序。你可以完成若干次下述操作，每次批次选择若干对邻近的$10$，将其全部替换成$01$。问至少需要多少次操作才能让整个序列有序。

这个问题和问题1不同，原因是它每次可以批量交换。但是由于是01序列，因此批量交换的规则也简单不少。

我们可以从左到右枚举$0$的位置，记第$i$个$0$前面有$p_i$个$1$，至少需要$r_i$轮操作才能将其移动到所有$1$之前。

对于序列前面的$0$，我们可以将其删除，不影响结果。可以发现对于第$i$个$0$，由于其前面有$p_i$个$1$，而每一轮操作它最多越过一个$1$，因此至少需要操作$p_i$轮，但是这里还需要分两种情况讨论，如果在抵达之前接触到了第$i-1$个$0$，由于不可能越过它，因此我们的操作次数应该至少为$r_{i-1}+1$，没有遇到，那么操作次数仅受前面$1$的数目所限制。因此第$i$个$0$抵达所有$1$前操作次数为$\max(r_{i-1}+1,p_i)$。

推荐一道题目：SRM783 CardboardBoxes。

问题8：给定一个长度为$n$的置换，允许每次交换两个相邻的元素，要求你用最少的次数将其整理为一个前面部分递增后面部分递减的序列，允许前面部分或后面部分为空。其中$1\leq n\leq 10^6$。

提供一道题目。

我们可以将后面的数$x$修改为$\infty-x$，这样问题就变成了标准的使序列递增的问题。那么现在我们首先需要选择一个子集，将子集中的元素全部修改。如何确定这个子集成为了唯一的问题。

当我们考虑转换一个元素时，我们定义$-x$为元素$x$的偏移，那么每个逆序对$(u,v)$的费用，我们将它赋予给偏移较大的元素。因此对每个元素$x$我们可以单独考虑。如果$x$被转换，则费用会减去前面偏移比它小的元素数目，同时加上后面偏移比它小的元素数目。因此我们可以直接确定每个元素是否被转换。

最后跑一次标准求逆序对的算法即可。总的时间复杂度为$O(n\log_2n)$。

字符串转换最少交换次数

给定长度为$n$的字符串$s$和$t$，每个字符在两个字符串中出现次数相同。现在要求你通过下面操作将字符串$s$转换成$t$。

• 每次挑选一个$i$，满足$1\leq i<n$，交换$s_i$和$s_{i+1}$。

问最少需要执行多少次操作。

首先我们交换的两个相邻字符肯定是不同的，因此我们知道$s_i$实际对应的是$t_{\pi(i)}$。

下面我们重新来解读这个问题，有一个置换$a_1,\ldots,a_n$，其中$a_i=\pi(i)$，要求我们通过邻位交换的技术将数组进行排序。这个问题我们实际上已经提到过了，就是排序最少交换次数。

提供一道题目。