本篇是 偏序序列变换规律再探 的续篇。

前面对 LR 型序列的变换规律有一些探讨，并给出了特性 8 的结论：gap(LR) = min{game(L), game(R)}。

看一个 game(L) < game(R) 的变换实例：

例 1：L = [1,1)[1,3)[1,1)，R = [4,1)[1,1)[2,1)，game(L) = 2，game(R) = 4

LR >> (1)[1,1)[1,3) [4,1)[1,1)[2,1)[1] >> (2)[1,1)[1,2) [3,1)[1,1)[2,1)[2] >> (3)[1,1)[1,1)[2,1)[1,1)[2,1)[3]

这个例子可以直观地看到，当 game(L) < game(R) 时，LR 经若干次变换后会由 LR 型变成 R 型。

同样，当 game(L) > game(R) 时，LR 经若干次变换后会由 LR 型变为 L 型。特别地，当 game(L) = game(R) 时，LR 型序列经若干次变换后会由 LR 型变为双一序列。

考察两个 LR 型序列拼接的情形，如：

例 2：L₁R₁ = [1,8)[1,1)[2,1)，L₂R₂ = [1,3)[1,1) [4,1)[2,1)，game(L₁) = 7，game(R₁) = 1，game(L₂) = 2，game(R₂) = 4

L₁R₁L₂R₂ // forts = 1

>> (1) [1,8)[2,1) E [1,3)[4,1)[2,1) [1] // forts = 3

>> (2) [1,7)[1,1) E² [1,2)[3,1)[2,1) [2] // forts = 2

>> (3) [1,7)[1,1) E² [1,1)[2,1)[2,1) [3]

...

>> (7)[1,7)[2,1)[2,1) [7] // forts = 2

>> (8)[1,6)[1,1)[2,1) [8]

>> (9)[1,6)[2,1) [9] // forts = 2

>> (10)[1,5)[1,1)[10]

这个例子里，game(L₁) > game(R₁)，game(L₂) < game(R₂)，从第 2 次变换结果看到 L₁R₁ 对应的序列已经变成了 L 型，记为 L'，从第 3 次变换结果看到 L₂R₂ 对应的序列已经变成了 R 型，记为 R'，L 型和 R 型组成新的 LR 型序列（第 2 次变换后的结果其实就已经是 LR 型），之后的变换还会形成跳变数。

本例中，由特性 12 可知 gap(L₁R₁L₂R₂) = 3-1 + (2-1)·3 = 5

另一方面，由特性 8 有 gap(L₁R₁) = min{7,1} = 1，gap(L₂R₂) = min{2,4} = 2

game(L') = game(L₁) - game(R₁) = 7-1 = 6，

game(R') = game(R₂) - game(L₂) = 4-2 = 2，

gap(L'R') = min{game(L'),game(R')} = min{6,2} = 2

即有 gap(L₁R₁L₂R₂) = gap(L₁R₁) + gap(L₂R₂) + gap(L'R')

把这个例子的两个 LR 型位置互换，因为 gap(R'L') = 0，则有 gap(L₂R₂L₁R₁) = gap(L₁R₁) + gap(L₂R₂) 。

再考察一个更多 LR 型序列拼接的例子：

例 3：L₁R₁ = [1,5)[1,1)[1,4) [2,1)[3,1) ，L₂R₂ = [1,2)[1,3) [5,1)[3,1)，L₃R₃ = [1,2)[1,2) [5,1)[2,1)

用 {game(L), game(R)} 来表示 LR 型序列对应的博弈值对。

V = L₁R₁L₂R₂L₃R₃

    =     [1,5)[1,1)[1,4) [2,1)[3,1)     [1,2)[1,3) [5,1)[3,1)     [1,2)[1,2) [5,1)[2,1)

            {7,3}                                    {3,6}                           {2,5}

>> (1) [1,5)[1,1)[1,3) [1,1)[3,1) E  [1,2)[1,2) [4,1)[3,1) E  [1,2)E [4,1)[2,1) [1]

            {6,2}                                    {2,5}                           {1,4}

>> (2) [1,5)[1,1)[1,3) [3,1) E²       [1,2)E [3,1)[3,1) E²     [1,2) [4,1)[2,1) [2]

            {6,2}                                    {1,4}                           {1,4}

>> (3) [1,5)[1,1)[1,2) [2,1) E³       [1,2) [3,1)[3,1) E³        E [3,1)[2,1) [3]

            {5,1}                                    {1,4}                           {0,3}

 = (3) [1,5)[1,1)[1,2) [2,1) E³       [1,2) [3,1)[3,1)E⁴[3,1)[2,1) [3]

            {5,1}                                    {1,7}

>> (4) [1,5)[1,1)[1,1) [1,1) E⁴       E [2,1)[3,1)E⁴[3,1)[2,1) [4]

            {4,0}                                    {0,6}

 = (4) [1,5)E⁸ [2,1)[3,1)E⁴[3,1)[2,1) [4]

            {4,6}

如上所示 ，组成序列 V 的 3 个 LR 型序列最初的博弈值对分别为 {7,3}、{3,6}、{2,5}，第一次变换得到 Γ(V)，依然由 3 个 LR 型序列组成，对应的博弈值对分别为 {6,2}、{2,5}、{1,4}，这次变换有 3 次博弈值对消减，即有 gap(V >> Γ(V)) = 3。

事实上，对任意 M 型序列 N，由 N 到 Γ(N) 这一次变换的博弈值对消减次数，记为 cuts(N >> Γ(N))，满足 cuts(N >> Γ(N)) = forts(N) - 1 = gap(N >> Γ(N))。用 LR 型序列的连通性很好说明这个结论：N 中不连通的 LR 型序列个数 n 就等于 cuts(N >> Γ(N))，而 forts(N) = n + 1。

继续例 3 的分析，由 Γ(V) 到 Γ²(V) 的变换，只有第二组 LR 型序列的博弈值对发生了消减，即从 {2,5} 消减为 {1,4}，因而有 gap(Γ(V) >> Γ²(V)) = 1。

同样，由 Γ²(V) 到 Γ³(V) 的变换， 有两组 LR 型序列的博弈值对发生了消减，即 gap(Γ²(V) >> Γ³(V)) = 2。此时，三组博弈值对分别为 {5,1}、{1,4}、{0,3}，最后一组的左元已经消减为 0，即对应的序列已经蜕化为 R 型序列，进而会和它左邻的 LR 型序列拼成一个新的 LR 型序列，如上面梅色高亮部分所示，新合成的 LR 型序列对应的博弈值对为 {1,4} {0,3} = {1,7}。

随后的 Γ³(V) 到 Γ⁴(V) 的变换， 两组博弈值对都发生了消减，即 gap(Γ³(V) >> Γ⁴(V)) = 2。此时，两组博弈值对分别为 {4,0}、{0,6}，说明对应的序列分别蜕化为 L 型序列和 R 型序列，它们进而合成新的 LR 型序列，其对应的博弈值对为 {4,0} {0,6} = {4,6}，由特性 8 知 这个新合成的序列的跳变数为min{4,6} = 4。

 从上面的分析过程看，这里实际上找到了通过累计博弈值对消减次数来计算任意 M 型序列的跳变数的一种简便方法。即在例 3 里有 gap(V) = 3+1+2+2+4 = 12。甚至可以以博弈值对指代 LR 型序列来进一步简化上面例子里的变换过程：

{7,3} {3,6} {2,5} >> {6,2} {2,5} {1,4} >> {6,2} {1,4} {1,4} >> {5,1} {1,4} {0,3} = {5,1} {1,7} >> {4,0} {0,6} = {4,6}

需要指出的是对应博弈值对 {a,b} 的 LR 型序列有无数多个（因为 E 值对的博弈值为 0，可以任意叠加），比如本例中对应 {7,3} 的 LR 型序列是 [1,5)[1,1)[1,4)[2,1)[3,1)，同样对应 {7,3} 的 LR 型序列有 [1,8)[4,1)、[1,8)[1,1)[4,1) 等。保持例 3 中三个博弈值对不变，而把对应的序列换成最少偏序值对数的 LR 型序列，即有

V’ = [1,8)[4,1) [1,4)[7,1) [1,3)[6,1)，则 V' 的连续变换过程为：

V'  =   [1,8)[4,1)      [1,4)[7,1)     [1,3)[6,1)

            {7,3}             {3,6}            {2,5}

>> (1) [1,7)[3,1) E  [1,3)[6,1) E  [1,2)[5,1) [1]

            {6,2}             {2,5}            {1,4}

>> (2) [1,6)[2,1) E²  [1,2)[5,1) E²  [1,1)[4,1) [2]

            {5,1}             {1,4}            {0,3}

= (2) [1,6)[2,1) E²  [1,2)[5,1)E³[4,1) [2]

            {5,1}             {1,7}

>> (3) [1,5)[1,1) E³  [1,1)[4,1)E³[4,1) [3]

            {4,0}             {0,6}

= (3) [1,5)E⁵[4,1)E³[4,1) [3]

            {4,6}

对比 V' 和 V 的连续变换过程发现，到达对应 {4,6} 的序列，V' 比 V 少用了一次变换，但 gap(V') = 3+3+2+4 = 12，即有 gap(V') = gap(V)。用博弈值对序列表示的变换过程为： 

{7,3} {3,6} {2,5} >> {6,2} {2,5} {1,4} >> {5,1} {1,4} {0,3} = {5,1} {1,7} >> {4,0} {0,6} = {4,6}    ①

gap({7,3} {3,6} {2,5}) = 3+3+2+4 = 12

 

换一个角度来看例 3 中的 {7,3} {3,6} {2,5}。无论具体经过多少次变换，博弈值对 {7,3} 最终会变化到 {4,0}，这个过程中 {7,3} 发生了 3 次消减；同样，{3,6} 经 3 次消减到 {0,3}，{2,5} 经 2 次消减到 {0,3}。即 {7,3} {3,6} {2,5} 经 3+3+2 = 8 次消减到 {4,0} {0,3} {0,3}；然后 {4,0} {0,3} {0,3} 合并为 {4,6}；最后 {4,6} 经 4 次消减到 {0,2}。整个过程可以表示为：

{7,3} {3,6} {2,5}

 ↓3     ↓3     ↓2

{4,0} {0,3} {0,3} = {4,6}

                              ↓4

                             {0,2}

gap({7,3} {3,6} {2,5}) = 3+3+2+4 = 12

这是一种新的累计博弈值对消减次数的方法，上面的方法（如 ① 所示）称作横向累计法，这里的方法称作纵向累计法。

来看用纵向累计法计算大型 M 型序列的一个例子：

例 4：X 为 M 型序列，对应的博弈值对序列为 {500,666} {45,60} {678,234} {777,123} {1111,5678} {345345,1234}，求 gap(X)。

{500,666} {45,60} {678,234} {777,123} {1111,5678} {345345,1234}

   ↓500       ↓45        ↓234          ↓123      ↓1111           ↓1234

{0,166}     {0,15}     {444,0}    {654,0}     {0,4567}       {344111,0} = {1098,4567}

                                                                                                             ↓1098

                                                                                                            {0,4567-1098}

gap(X) = 500+45+234+123+1111+1234+1098。

 

一个 LR 型序列的博弈值对为 {a,b}，a > 0，b > 0，则称该序列为 {a,b} 型序列。

综合上面的分析，有如下两个特性：

特性 16（{a,b} 型序列变换特性）：构成 M 型序列 V 的单个 {a,b} 型序列 X 在 V 到 Γ(V) 的变换中满足如下规律：

I. 若 X 是连通的，则变换后得到的新序列 Y 依然是 {a,b} 型序列，即没有发生博弈值对消减；

II. 若 X 是不连通的，则变换后得到的新序列 Y 的博弈值对为 {a-1,b-1}，即发生了一次博弈值对消减，按 a 和 b 的取值不同，又细分为四种子情形：

（1）若 a > 1 且 b > 1，则 Y 是 {a-1,b-1} 型序列；

（2）若 a > 1 且 b = 1，则 Y 蜕化成 L 型序列，如果它的右邻是 LR 型或 R 型序列，则可以和右邻合成新的 LR 型序列；

（3）若 a = 1 且 b > 1，则 Y 蜕化成 R 型序列，如果它的左邻是 LR 型或 L 型序列，则可以和左邻合成新的 LR 型序列；

（4）若 a = 1 且 b = 1，则 Y 蜕化成双一序列，如果它的左邻（或右邻）是 LR 型序列，则可以和左邻（或右邻）合成新的 LR 型序列。

特性 17（M 型序列变换特性）：两个 M 型序列 M₁ = L₁R₁ ... L_kR_k，M₂ = L'₁R'₁ ... L'_kR'_k，且满足 game(L_i) = game(L'_i)，game(R_i) = game(R'_i)，i=1,...,k。则 gap(M₁) = gap(M₂)。

 

为证明特性 11，先证明如下的引理：

X 和 Y 是纯值对序列，且都是可生成偏序序列，则一定有  gap(XEY) = gap(XY)。

证明：由上篇的分析知，X 和 Y 各自可以有 7 种形式，即 L 型、R 型、RL 型、M 型、ML 型、RM 型和 RML 型序列。

由特性 14 知，当 X 为 R 型序列时，显然有 gap(XEY) = gap(XY) 成立；而当 X 为 RA 形式（RL 型、RM 型、RML 型的统称）时，有 gap(RAEY) = gap(AEY)。因而只需考虑 X 为 3 种形式：L 型、M 型和 ML 型。

同样，对于 Y，也只需考虑 3 种形式：R 型、M 型和 RM 型。这样需要考虑 XEY 的 9 种组合情形：

(I). LER

由特性 8，显然有 gap(LER) = gap(LR)。

(II). LEM

记 M = L₁R₁ L₂R₂ ... L_kR_k，则 LM = LL₁R₁ L₂R₂ ... L_kR_k，LEM = LEL₁R₁ L₂R₂ ... L_kR_k

即 LM 和 LEM 也都是由 k 个 LR 型序列组成的 M 型序列，且只有构成第一个 LR 型序列的左一序列是不一样的，前者是 LL₁，后者是 LEL₁。由博弈值定义显然有 game(LL₁) = game(LEL₁)，再由特性 17，有 gap(LEM) = gap(LM)。

(III). LERM

LERM 和 LRM 显然都是 M 型序列，且都是在 M 序列的左侧增加了一个 LR 型序列，前者是 LER，后者是 LR，且有 game(LE) = game(L)，于是由特性 17，有 gap(LERM) = gap(LRM)。

(IV). MER

记 M = L₁R₁ L₂R₂ ... L_kR_k，则 MER = L₁R₁ L₂R₂ ... L_kR_kER，MR = L₁R₁ L₂R₂ ... L_kR_kR，显然 MER 和 MR 也都是由 k 个 LR 型序列组成的 M 型序列，且只有构成第 k 个 LR 型序列的右一序列是不一样的，前者是 R_kER，后者是 R_kR。game(R_kER) = game(R_kR)，由特性 17，有 gap(MER) = gap(MR)。

(V). M₁EM₂

 记 M₁ = L₁R₁ L₂R₂ ... L_kR_k，M₂ = L'₁R'₁ L'₂R'₂ ... L'_gR'_g，显然 M₁EM₂ 和 M₁M₂ 都是由 k+g 个 LR 型序列组成的 M 型序列，且只有构成第 k 个 LR 型序列的右一序列是不一样的，前者是 R_kE，后者是 R_k。game(R_kE) = game(R_k)，由特性 17，有 gap(M₁EM₂) = gap(M₁M₂)。

(VI). M₁ERM₂

记 M₁ = L₁R₁ L₂R₂ ... L_kR_k，M₂ = L'₁R'₁ L'₂R'₂ ... L'_gR'_g，显然 M₁ERM₂ 和 M₁RM₂ 都是由 k+g 个 LR 型序列组成的 M 型序列，且只有构成第 k 个 LR 型序列的右一序列是不一样的，前者是 R_kER，后者是 R_kR。game(R_kER) = game(R_kR)，由特性 17，有 gap(M₁ERM₂) = gap(M₁RM₂)。

(VII). MLER

MLER 和 MLR 显然都是 M 型序列，且都是在 M 序列的右侧增加了一个 LR 型序列，前者是 LER，后者是 LR，且有 game(LE) = game(L)，由特性 17，有 gap(MLER) = gap(MLR)。

(VIII). M₁LEM₂

记 M₁ = L₁R₁ L₂R₂ ... L_kR_k，M₂ = L'₁R'₁ L'₂R'₂ ... L'_gR'_g，显然 M₁LEM₂ 和 M₁LM₂ 都是由 k+g 个 LR 型序列组成的 M 型序列，且只有构成第 k+1 个 LR 型序列的左一序列是不一样的，前者是 LEL'₁，后者是 LL'₁。game(LEL'₁) = game(LL'₁)，由特性 17，有 gap(M₁LEM₂) = gap(M₁LM₂)。

(IX). M₁LERM₂

记 M₁ = L₁R₁ L₂R₂ ... L_kR_k，M₂ = L'₁R'₁ L'₂R'₂ ... L'_gR'_g，显然 M₁LERM₂ 和 M₁LRM₂ 都是由 k+g+1 个 LR 型序列组成的 M 型序列，且只有构成第 k+1 个 LR 型序列的左一序列是不一样的，前者是 LE，后者是 L。game(LE) = game(L)，由特性 17，有 gap(M₁LERM₂) = gap(M₁LRM₂)。

证毕。

 

以下证明特性 11：

从一个纯值对序列 U 中剔除全部双一值对后，得到的序列 V 必然满足 gap(U) = gap(V)。

证明：若 U = EV 或 U = VE，由特性 15 显然有 gap(U) = gap(V)。剩余只需证明：

若 U = XEY，其中 U、X、Y 均为纯值对序列，则 gap(U) = gap(XY)。

Γ(U) = Γ(X)(1) [1]Γ(Y)，Γ(XY) = Γ(X) Γ(Y)

由特性 9 知，Γ(U) 和 Γ(XY) 都不含有 I 型值对。

以下分情形考虑：

(I). 当 right(X) = 1，left(Y) = 1 时

forts(XY) = forts(X) + forts(Y) - 1 = forts(U)

可记 Γ(X) = (a)X'[1]，Γ(Y) = (1)Y'[b]

于是 Γ(XY) = (a)X'EY'[b]，Γ(U) = (a)X'EEY'[b]，由上述引理有 gap(Γ(U)) = gap(Γ(XY))，结合 forts(U) = forts(XY)，便有 gap(U) = gap(XY)。

(II). 当 right(X) = 1，left(Y) > 1 时

同样有 forts(XY) = forts(X) + forts(Y) - 1 = forts(U)

可记 Γ(X) = (a)X'[1]，Γ(Y) = Y'[b]

于是 Γ(XY) = (a)X' [1]Y'[b]，Γ(U) = (a)X'E [1]Y'[b]，由上述引理有 gap(Γ(U)) = gap(Γ(XY))，结合 forts(U) = forts(XY)，便有 gap(U) = gap(XY)。

(III). 当 right(X) > 1，left(Y) = 1 时

同样有 forts(XY) = forts(X) + forts(Y) - 1 = forts(U)

可记 Γ(X) = (a)X'，Γ(Y) = (1)Y'[b]

于是 Γ(XY) = (a)X'(1) Y'[b]，Γ(U) = (a)X'(1) EY'[b]，由上述引理有 gap(Γ(U)) = gap(Γ(XY))，结合 forts(U) = forts(XY)，便有 gap(U) = gap(XY)。

(IV). 当 right(X) > 1，left(Y) > 1 时

Γ(X) 的最右边不会发生右析出，Γ(Y) 的最左边也不会发生左析出，即有

forts(XY) = forts(X) + forts(Y) = forts(U) + 1

可记 Γ(X) = (a)X'，Γ(Y) = Y'[b]

于是 Γ(XY) = (a)X'Y'[b]，Γ(U) = (a)X'(1) [1]Y'[b]。

由 X'(1) [1]Y' 不含 I 型值对可知：

X'(1) 末尾的偏序值对为 [1,p)，X' 末尾的偏序值对为 [1,p-1)，p = right(X)；

[1]Y' 开头的偏序值对为 [q,1)，Y' 开头的偏序值对为 [q-1,1)，q = left(Y)。

可记 X' = R₁M₁L₁[1,p-1)，Y' = [q-1,1)R₂M₂L₂，其中 R₁、R₂ 为右一序列或者空序列；M₁、M₂ 为 M 型序列或者空序列；L₁、L₂ 为左一序列或者空序列。

于是 X'Y' = R₁M₁L₁[1,p-1)[q-1,1)R₂M₂L₂，X'(1) [1]Y' = R₁M₁L₁[1,p)[q,1)R₂M₂L₂

记 L = L₁[1,p-1)，L' = L₁[1,p)，R = [q-1,1)R₂，R' = [q,1)R₂

再记 N₁ = M₁LRM₂，N₂ = M₁L'R'M₂

由特性 14 有 gap(Γ(XY)) = gap(N₁)，gap(Γ(U)) = gap(N₂)

假设 M₁ 和 M₂ 分别由 k 个和 g 个 LR 型序列组成，易知 N1 和 N2 都是由 k+g+1 个 LR 型序列组成的 M 型序列，且只有第 k+1 个 LR 型序列不同，前者是 LR，后者是 L'R'。

由 L 和 L' 的定义易知，game(L') = game(L) + 1；由 R 和 R' 的定义易知，game(R') = game(R) + 1

LR 对应的博弈值对为 {game(L), game(R)}，L'R' 对应的博弈值对为 {game(L)+1, game(R)+1}

记 c = min{game(L), game(R)}，由前述的纵向累计法可知 LR 经 c 次消减到对应 {game(L) - c, game(R) - c} 的蜕化序列，而 L'R' 经 c+1 次消减到对应 {game(L) - c, game(R) - c} 的蜕化序列。随后轮次的博弈值对合并与消减则完全一致，从而有 gap(N₂) - gap(N₁) = c+1 - c = 1，即

gap(Γ(U)) - gap(Γ(XY)) = 1，结合 forts(XY) = forts(U) + 1，可知

gap(U) = gap(XY)。

证毕。

 

最后看一个运用上述特性的综合例子：

例 5：U = [4,5)[4,1)[1,3)[1,1)[3,4)[1,1)[1,5)[6,4)，求 ω(U)。

1）因为要求 ω(U) 的值，先求 F(U)

F(U) = 8+4+3+1+6+1+5+9 = 37

2）把 U 的左右界置为 1，并去除 E 值对，得 U' = [1,5)[4,1)[1,3)[3,4)[1,5)[6,1)

由特性 10 和特性 11 知，gap(U') = gap(U)

3）对 U' 做堡垒划分：U' = [1,5)  [4,1)[1,3)  [3,4)[1,5)  [6,1)，得 forts(U') = 4

4）对 U' 做变换：Γ(U') = (1) [1,4)  [3,1)E[1,2)  [2,1)[1,4)[1,4)  [5,1) [1]

5）对 pure(Γ(U')) 中的 M 型序列做去 E 和 LR 型序列划分处理，得

M = [1,4)  [3,1)      [1,2)  [2,1)      [1,4)[1,4)  [5,1)

6）用纵向累计法求 序列 M 的跳变数

      {3,2}               {1,1}               {6,4}

       ↓2                   ↓1                  ↓4

      {1,0}               {0,0}               {2,0} = {3,0}

gap(M) = 2+1+4 = 7

7）求出gap(U)

gap(U) = gap(U') = forts(U') - 1 + gap(Γ(U')) = 4 - 1 + gap(M) = 3 + 7 = 10

8）求出 ω(U) 

ω(U) = F(U) - gap(U) = 37 - 10 = 27

即 序列 U 要经历 27 次 Γ 变换后成为规范序列。