K 连续位的最小翻转次数:群论解释

March 01, 2019

LeetCode 第 995 题:一个只包含 0011 的序列,只能通过连续 KK 位的翻转,能否变为全是 11 的序列?如果能,最少需几次?

例如 01011000101100,只允许连续 K=3K = 3 次的翻转,通过如下 44 次翻转变成全为 11 的序列:

010110010111001100100111100011111110101100 \rightarrow 1011100 \rightarrow 1100100 \rightarrow 1111000 \rightarrow 1111111

问题的解法是,从最左边开始寻找第一个 00

  • 没有 00,问题已解决;
  • 从这个 00 处尝试翻转 KK

    • 剩余不足 KK 位,返回错误
    • 翻转后,继续循环寻找列表的第一个 00

这个算法为什么是对的?

“翻转”群

以如上的 01011000101100 为例,其上所有的翻转(不只考虑连续的)是从一个 77 位序列到另一个 77 位序列上的映射,我们把翻转第 a1,a2,...,ana_1,a_2,...,a_n 位记作 Fa1,a2,...,anF_{a_1,a_2,...,a_n}

比如翻转 3,4,63,4,6 位的翻转 F346F_{346}F346(0101100)=0110110F_{346}(0101100) = 0110110

翻转的复合即两次翻转,比如先进行 F346F_{346},再进行 F236F_{236}

F236(F346(0101100))=0000100F_{236}(F_{346}(0101100)) = 0000100

实际上这和进行一次 F24F_{24} 翻转等价:

F24(0101100)=0000100F_{24}(0101100) = 0000100

因为左边把翻转了两次第 3366 位,相当于不翻转。

容易得知这个 77 位序列上的所有翻转构成一个 Abel 群,翻转的复合为二元运算,单位元 II 为“不翻转”,每个翻转的逆元等于它本身。

翻转的复合本质上就是求集合的对称差:保留那些只出现一次的翻转位。

集合 {1,2,3,4,5,6,7}\{1,2,3,4,5,6,7\} 上所有子集在对称差运算下也构成一个 Abel 群,二元运算为集合的对称差运算,单位元为 \varnothing。这个群与翻转群同构:翻转 Fa1,a2,...,anF_{a_1,a_2,...,a_n} 与集合 {a1,a2,...,an}\{a_1,a_2,...,a_n\} 一一对应。

连续翻转

77 位序列上的 33 位连续翻转只有如下 55 个:

F123,F234,F345,F456,F567F_{123}, F_{234}, F_{345}, F_{456}, F_{567}

题目所求即为使用以上 55 个映射,复合出从 F1367F_{1367}( 即映射 010110011111110101100 \rightarrow 1111111 )。假如我们构造出一种翻转方法:使用 aaF123F_{123}bbF567F_{567},再 ccF123F_{123}ddF567F_{567},即

F567dF123cF567bF123aF_{567} ^ d \circ F_{123} ^ c \circ F_{567} ^ b \circ F_{123} ^ a

它对应于上面所说的“翻转”群里的某个映射,现在我们要使用这个 Abel 群的美好性质了!

由交换律和结合律有

F567dF123cF567bF123a=F567dF567bF123cF123a=F567b+dF123c+aF_{567}^d \circ F_{123}^c \circ F_{567}^b \circ F_{123}^a = F_{567}^d \circ F_{567}^b \circ F_{123}^c \circ F_{123}^a = F_{567}^{b+d} \circ F_{123}^{c+a}

其中交换律意味着复合结果和使用翻转的顺序无关!

结合律意味着对某一翻转先 xx 次,再 yy 次等价于 x+yx+y 次。

现在最美好的性质来了:这个群中所有元素的逆元等于本身。

如果 xx 是奇数,那么 F123x=F123F_{123}^{x} = F_{123},如果 xx 是偶数,那么 F123x=IF_{123}^{x} = I

经过如上三种变换,任何以这 55 种连续翻转复合而成的映射都可以化为如下形式:

F123aF234bF345cF456dF567e (a,b,c,d,e{0,1})F_{123}^a \circ F_{234}^b \circ F_{345}^c \circ F_{456}^d \circ F_{567}^e ~(a,b,c,d,e \in \{0,1\})

即每种连续翻转我们只用考虑用或者不用。如果用,也只用一次就够了。

问题约化

我们的问题等价于求解 (其中 a,b,c,d,e{0,1}a,b,c,d,e \in \{0,1\} ),

F1367=F123aF234bF345cF456dF567eF_{1367} = F_{123}^a \circ F_{234}^b \circ F_{345}^c \circ F_{456}^d \circ F_{567}^e

先来看 aa:由于只有 F123F_{123} 包含第 11 位,所以 a=1a = 1,于是

F1367=F123F234bF345cF456dF567eF_{1367} = F_{123} \circ F_{234}^b \circ F_{345}^c \circ F_{456}^d \circ F_{567}^e

两边同乘以 F123F_{123}

F1367F123=(F123F123)F234bF345cF456dF567eF_{1367} \circ F_{123} = (F_{123} \circ F_{123}) \circ F_{234}^b \circ F_{345}^c \circ F_{456}^d \circ F_{567}^e

因为 F123F123=IF_{123} \circ F_{123} = I,消去得到,

F267=F234bF345cF456dF567eF_{267} = F_{234}^b \circ F_{345}^c \circ F_{456}^d \circ F_{567}^e

计算 bb:同理,只有 F234F_{234} 包含第 22 位,所以 b=1b=1,(此时我们其实也可以计算 ee,因为只有它包含第 77 位),如此重复此过程。

当此过程结束时,等式右边必然是 II,如果:

  • 左边等于 II,此时位序列没有 00,构造成功,最少步数即为我们使用的连续翻转的次数;

  • 左边不等于 II,此时位序列中还有 00,则构造失败,无法复合出满足条件的映射来。