邻位交换问题

Published: by Creative Commons Licence

  • Tags:

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后形成的连通块的不平衡度,称为边两端不平衡度。 很显然式子 是结果的一个下界。我们可以这样理解这个式子,由于删除$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,2,\ldots,n$的置换序列$a_1,\ldots,a_n$,每一次操作是交换两个相邻的数,问最少需要多少次操作才能将序列排序。

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

要统计逆序对,可以利用BIT。时间复杂度为$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)$,要求我们通过邻位交换的技术将数组进行排序。这个问题我们实际上已经提到过了,就是排序最少交换次数。

提供一道题目