組合循環(huán)生成法在柯克曼三元系中的應(yīng)用

謝玉枚，楊 瑋，高海燕

（1.福建江夏學(xué)院電子信息科學(xué)學(xué)院，福建 福州 350108，2.廈門(mén)理工學(xué)院電氣工程與自動(dòng)化學(xué)院，福建 廈門(mén) 361024）

1850年，英國(guó)教會(huì)的教區(qū)長(zhǎng)柯克曼Kirkman提出：一位女教師每天都帶領(lǐng)著她的15位女學(xué)生去散步，她要求學(xué)生們排成三人一組，一共五組的隊(duì)列隨她前進(jìn)，問(wèn)能否給出一個(gè)一周內(nèi)的隊(duì)列安排，使得每?jī)擅麑W(xué)生在七天中都恰有一天排在同一組。

從柯克曼于1850年提出女生散步問(wèn)題至今，眾多學(xué)者和愛(ài)好者對(duì)柯克曼三元系的構(gòu)造問(wèn)題進(jìn)行了許多研究和探討，它開(kāi)創(chuàng)了組合設(shè)計(jì)的先河，其中BIBD表示為B[k,λ；v]是組合設(shè)計(jì)最重要的一類(lèi)。它指的是v元集V中一些K-子集（稱(chēng)為區(qū)組）的族β使得V的每個(gè)2-子集都恰好出現(xiàn)于β的λ個(gè)區(qū)組中[1]。 當(dāng)k=3，λ=1時(shí)，這種設(shè)計(jì)被稱(chēng)為斯坦納（Steiner）三元系，記作STS(v)，STS(v)存在的充分必要條件為當(dāng)且僅當(dāng)v≡1 or 3(mod 6)[2]。如果β可拆分為若干個(gè)子族，使得每個(gè)子族都構(gòu)成集合V的一個(gè)分拆，則稱(chēng)其為可分解的斯坦納三元系，用KTS(v)表示，KTS(v)存在的充分必要條件為當(dāng)且僅當(dāng)v≡3(mod 6)。

迄今為止，眾多學(xué)者對(duì)BIBD進(jìn)行了大量研究，并且提出了構(gòu)造STS(v)和KTS(v)的遞歸方法。其中一種經(jīng)典方法為Chaudhuri和Wilson等[2]、Hanani等[3]提出的基于柯克曼框架來(lái)構(gòu)造柯克曼三元系；另外一種方法是使用分組設(shè)計(jì)來(lái)解決BIBD的構(gòu)建問(wèn)題[4-6]。在這些構(gòu)造方法中，循環(huán)BIBD和單旋轉(zhuǎn)BIBD由于它們的代數(shù)結(jié)構(gòu)簡(jiǎn)單且實(shí)用性強(qiáng)，許多學(xué)者對(duì)其進(jìn)行了大量的研究，其中Phelps等[7]首先介紹了單旋轉(zhuǎn)STS(v)的概念，Jimbo等提出了遞歸構(gòu)造方法來(lái)構(gòu)造1-旋轉(zhuǎn)S teiner-2設(shè)計(jì)和可解析的1-旋轉(zhuǎn)Steiner-2設(shè)計(jì)[8-10]。這些方法都是使用群論、圖論和代數(shù)工具來(lái)解決BIBD的構(gòu)造問(wèn)題。

最近有學(xué)者提出了從不同的角度解決STS(v)和KTS(v)的研究。例如，將柯克曼女生散步問(wèn)題作為社會(huì)高爾夫球手問(wèn)題的特定實(shí)例，可以通過(guò)約束編程[11]和約束滿(mǎn)足問(wèn)題[12]來(lái)解決。Barnier[13]提出了一種檢查對(duì)稱(chēng)性的算法，并在幾秒鐘內(nèi)解決了柯克曼的女學(xué)生問(wèn)題。Lardeux等[14]通過(guò)表達(dá)模型化集合約束問(wèn)題并將其自動(dòng)編碼為SAT實(shí)例來(lái)解決社交高爾夫球手問(wèn)題。

在本文中，從計(jì)算機(jī)科學(xué)的角度提出了一種遞歸構(gòu)造的KTS(v)新方法，通過(guò)建立一個(gè)用于構(gòu)造v≡3 mod 12的KTS(v)的模型，這不是文獻(xiàn)[13]中提出的集合模型，而是基于羅洪田[15]提出的將集合V的元素對(duì)應(yīng)于圓上的點(diǎn)的模型，將幾何圖形與區(qū)組結(jié)合起來(lái)，圓上的三角形作為KTS的區(qū)組，并提出了一種計(jì)算機(jī)算法來(lái)生成KTS(v)。

求解從n個(gè)元素中取m個(gè)元素的組合，可以把n個(gè)元素均勻分布在圓周上，這樣求解Cmn的組合就轉(zhuǎn)換為在等分圓周上求解m邊形。圓周上的m邊形沿著圓周轉(zhuǎn)動(dòng)可產(chǎn)生n個(gè)m邊形。例如，當(dāng)n=8，將8個(gè)數(shù)字均勻分布在等分圓周上，求解的組合情況就變換成在圓周上求解3邊形，如圖1所示，3邊形1-2-3沿著圓周轉(zhuǎn)動(dòng)可產(chǎn)生8個(gè)各不相同的3邊形，可以通過(guò)對(duì)3邊形1-2-3作數(shù)字循環(huán)寫(xiě)出其同構(gòu)3邊形，如表1所示。這8個(gè)3邊形有什么特點(diǎn)呢？它們的相鄰元素間距離相等，因此認(rèn)為它們結(jié)構(gòu)相同。

圖1 8等分圓

表1 3邊形123的同構(gòu)3邊形

將n個(gè)元素均勻分布在圓周上，圓周被分成n個(gè)弧段，兩個(gè)元素所夾的弧的段數(shù)稱(chēng)為弧長(zhǎng)。兩個(gè)元素所夾有大小兩個(gè)弧段，其和為n，現(xiàn)約定以小弧段代表弧長(zhǎng)，所以圓周上兩個(gè)元素的弧長(zhǎng)為：當(dāng)兩元素對(duì)應(yīng)的數(shù)字之差的絕對(duì)值小于等于n/2，弧長(zhǎng)等于數(shù)字之差；當(dāng)兩元素對(duì)應(yīng)的數(shù)字之差的絕對(duì)值大于n/2，弧長(zhǎng)等于n減去數(shù)字之差。

在n等分圓周上，當(dāng)n等于偶數(shù)時(shí)，基本的弧長(zhǎng)有n/2個(gè)，分別為：1,2,3，…，n/2；當(dāng)n等于奇數(shù)時(shí)，基本的弧長(zhǎng)有(n-1)/2 個(gè)，分別為：1,2,3，…，(n-1)/2。

用m邊形中的相鄰元素間的弧長(zhǎng)表示m邊形的結(jié)構(gòu)。例如，當(dāng)n=8，m=3時(shí)，3邊形123的結(jié)構(gòu)用(1,1,2)表示，其循環(huán)產(chǎn)生的8個(gè)3邊形的結(jié)構(gòu)也是(1,1,2)，且這8個(gè)3邊形各不相同，如表1所示。

在n=8等分圓周上，結(jié)構(gòu)不同的3邊形通過(guò)計(jì)算得到了7個(gè)不同結(jié)構(gòu)3邊形，如表2所示，這7個(gè)3邊形循環(huán)轉(zhuǎn)動(dòng)可分別產(chǎn)生8個(gè)不同的3邊形，于是8等分圓周上3邊形的總數(shù)為：8×7=56，恰好等于。

表2 的所有組合

表2 的所有組合

編號(hào)12345678(1,1,2)123234345456567678781812(1,2,3)235346457568671782813124(1,3,4)125236347458561672783814(1,4,3)126237348451562673784815(1,3,2)127238341452563674785816(2,2,4)246357468571682713824135(2,3,3)136247358461572683714825

從表2可知，當(dāng)n=8，m=3時(shí)，圓周上任意一個(gè)結(jié)構(gòu)的3邊形沿著圓周轉(zhuǎn)動(dòng)都能產(chǎn)生8個(gè)不相同的3邊形，從而的所有組合由不同結(jié)構(gòu)的3邊形分別沿著圓周循環(huán)轉(zhuǎn)動(dòng)產(chǎn)生。然而并不是對(duì)任意n和m，圓周上的m邊形沿著圓周轉(zhuǎn)動(dòng)都能產(chǎn)生n個(gè)不相同的3邊形，例如當(dāng)n=9時(shí)，將9個(gè)數(shù)字均勻分布在等分圓周上，3邊形1-4-7沿著圓周轉(zhuǎn)動(dòng)產(chǎn)生了9個(gè)3邊形，如表3所示。

表3 3邊形147轉(zhuǎn)動(dòng)產(chǎn)生的3邊形

從表3可以看出，3邊形1-4-7產(chǎn)生的9個(gè)3邊形中有3組重復(fù)項(xiàng)（表中√所示）。同時(shí)注意到求組合時(shí)，n與m有公因子3。是否可以作這樣的假設(shè)，在使用循環(huán)法求解時(shí)，當(dāng)n與m沒(méi)有公因子時(shí)，圓周上任意結(jié)構(gòu)的m邊形沿著圓周轉(zhuǎn)動(dòng)生成的n個(gè)m邊形是不相同的；當(dāng)n與m有公因子時(shí)，圓周上至少有一個(gè)m邊形沿著圓周轉(zhuǎn)動(dòng)生成的n個(gè)m邊形是有重復(fù)項(xiàng)的。

2 n與m的公因子

現(xiàn)令M=((n-1)(n-2)…(n-m+1))/m!，所以。

當(dāng)m與n有公因子r時(shí)，r可以同時(shí)被n與m整除，這就意味著，在n等分圓周上，m邊形中的m個(gè)元素可以被分為r塊，每一塊有m/r個(gè)元素，則m邊形可表示為(m1,m2,…,mr)，其中mi(1≦i≦r)為每塊之間的元素；n也可以被分為r組，每組之間的弧長(zhǎng)為n/r。當(dāng)m邊形(m1,m2,…,mr)，每個(gè)塊 mi結(jié)構(gòu)相同，相鄰mi間的弧長(zhǎng)相等為n/r時(shí)，m邊形沿著圓周移動(dòng)n/r個(gè)單位后，m邊形不變，因此m邊形沿著圓周轉(zhuǎn)動(dòng)一圈后會(huì)產(chǎn)生r個(gè)相同的m邊形。

當(dāng)公因子等于2時(shí)，4邊形中的4個(gè)元素就被分為2塊，每塊有2個(gè)元素，相鄰塊之間的弧長(zhǎng)為：8/2=4，令4邊形第一塊的第一個(gè)元素為1，因?yàn)橄噜弶K之間的弧長(zhǎng)為4，所以第二塊的第一個(gè)元素為5，所以這個(gè)4邊形可以寫(xiě)成1x 5y，其中2≤x≤4，6≤y≤8，且這兩塊的結(jié)構(gòu)相同，所以還得滿(mǎn)足y-5=x-1。于是可以得到滿(mǎn)足條件的3個(gè)4邊形，如表4所示，其中第1個(gè)和第3個(gè)4邊形結(jié)構(gòu)相同，它們都有2組重復(fù)項(xiàng)，如表4中√所示。而第2個(gè)4邊形不僅滿(mǎn)足公因子等于2的條件，如表4中√所示，同時(shí)還滿(mǎn)足公因子等于4的條件。

表4 的組合類(lèi)型

表4 的組合類(lèi)型

編號(hào)123456781(1,3,1,3)√1256347734784581√56126723783481452(2,2,2,2)√*13572468*35714682√*57136824*724682463(3,1,3,1)√1458256136724783√5814612573478347

當(dāng)公因子等于4時(shí)，4邊形中的4個(gè)元素就被分為4塊，每塊有1個(gè)元素，相鄰塊之間的弧長(zhǎng)為：8/4=2，令4邊形的第一塊的元素為1，因?yàn)橄噜弶K之間的弧長(zhǎng)為2，所以第二塊的元素為3，第三塊的元素為5，第四塊的元素為7，所以這個(gè)四邊形為1-3-5-7，沿著圓周轉(zhuǎn)動(dòng)可產(chǎn)生4組重復(fù)項(xiàng)，如表4中*所示。

當(dāng)n與m沒(méi)有公因子，在n等分圓周上，m邊形中的m個(gè)元素不能被分為整數(shù)塊，在轉(zhuǎn)動(dòng)過(guò)程中不會(huì)產(chǎn)生重復(fù)項(xiàng)，所以產(chǎn)生的n個(gè)m邊形是各不相同的。

定理1當(dāng)n與m沒(méi)有公因子時(shí)，將不同結(jié)構(gòu)的m邊形作循環(huán)可直接生成n×M個(gè)m邊形，這n×M個(gè)m邊形就是的所有組合，其中不同結(jié)構(gòu)的m邊形的個(gè)數(shù)為M，其中M=((n-1)(n-2)…(n-m+1))/m!，且當(dāng)n與m沒(méi)有公因子時(shí)，M一定為整數(shù)；

定理2當(dāng)n與m有公因子r時(shí)，至少存在一個(gè)m邊形作循環(huán)時(shí)產(chǎn)生r組重復(fù)項(xiàng)，的所有組合等于不同結(jié)構(gòu)的m邊形作循環(huán)同時(shí)去掉重復(fù)項(xiàng)。

3 m邊形相同結(jié)構(gòu)的判定

標(biāo)記m邊形時(shí)都是按順時(shí)針?lè)较蜻M(jìn)行的，m邊形中的m個(gè)點(diǎn)都可以作為起始點(diǎn)。例如，3邊形1-2-3，除了以1為起始點(diǎn)外，還可以以2和3為起始點(diǎn)，3邊形1-2-3，2-3-1和3-1-2是完全相等的，如表5所示，這3個(gè)3邊形和其結(jié)構(gòu)都隨著起始點(diǎn)的變化向左循環(huán)移動(dòng)。因此，若一個(gè)m邊形的結(jié)構(gòu)循環(huán)左移k（0≤k＜m）個(gè)單位后，與另一個(gè)m邊形的結(jié)構(gòu)相等，我們就判定這兩個(gè)m邊形的結(jié)構(gòu)相等。

表5 3邊形123向左循環(huán)移動(dòng)

通過(guò)兩個(gè)例子來(lái)說(shuō)明，在7等分圓周上，有3邊形2-3-7(1-3-2)和1-3-4(2-1-3)，3邊形237向左循環(huán)移動(dòng)2個(gè)單位后，其結(jié)構(gòu)與3邊形1-3-4(2-1-3)相等，如表6所示，因此這兩個(gè)3邊形的結(jié)構(gòu)相等。

表6 3邊形237向左循環(huán)移動(dòng)

同樣在7等分圓周上，有3邊形6-7-2(123)和3邊形1-3-4(213)，3邊形6-7-2循環(huán)左移過(guò)程中沒(méi)有找到與3邊形1-3-4(213)重合的結(jié)構(gòu)，如表7所示，因此這兩個(gè)3邊形的結(jié)構(gòu)不同。

表7 3邊形672向左循環(huán)移動(dòng)

4 求解不同結(jié)構(gòu)的m邊形

m邊形在圓周內(nèi)是封閉的，因此m邊形相鄰元素之間的弧長(zhǎng)之和應(yīng)該等于n。因?yàn)閮蓚€(gè)元素之間的弧長(zhǎng)是用小弧長(zhǎng)來(lái)表示的，所以圓周上的m邊形分為兩類(lèi)，第一類(lèi)m邊形的m個(gè)元素只分布在半圓內(nèi)，這類(lèi)m邊形相鄰元素之間的弧長(zhǎng)之和不等于n，m個(gè)弧長(zhǎng)中最大的弧長(zhǎng)等于其他m-1個(gè)弧長(zhǎng)之和且小于n/2；第二類(lèi)元素分布在整個(gè)圓內(nèi)，m邊形的m個(gè)弧長(zhǎng)之和等于n。例如，在8等分圓周上，3邊形1-2-3(112)的三個(gè)元素只分布在半圓內(nèi)，屬于第一類(lèi)3邊形；3邊形1-3-6(233)分布在整個(gè)圓內(nèi)，屬于第二類(lèi)，3個(gè)弧長(zhǎng)之和等于8。

計(jì)算m邊形的結(jié)構(gòu)可以轉(zhuǎn)化為一序列約束條件，令m邊形的結(jié)構(gòu)為(x1,x2，…，xm)，其中x1,x2，…，xm為m邊形的m個(gè)弧長(zhǎng)。因?yàn)閙邊形的結(jié)構(gòu)循環(huán)左移可產(chǎn)生m種等價(jià)結(jié)構(gòu)（如表5所示），使得在找出不同結(jié)構(gòu)的m邊形時(shí)還得排除等價(jià)的結(jié)構(gòu)，因此令m邊形(x1,x2，…，xm)的標(biāo)準(zhǔn)結(jié)構(gòu)為：最后一個(gè)弧長(zhǎng)xm最大，也就是x1≤x2≤…≤xm。

因?yàn)閙＜3時(shí)，m邊形的結(jié)構(gòu)可直接寫(xiě)出，所以以下的論述是針對(duì)m≥3的情況。

對(duì)于第一類(lèi)m邊形，xm為弧長(zhǎng)中最大的，則有下列約束：

對(duì)于第二類(lèi)m邊形，其m個(gè)元素分布在整個(gè)圓上，前m-1個(gè)弧長(zhǎng)之和大于等于n/2，且m邊形的標(biāo)準(zhǔn)結(jié)構(gòu)必須滿(mǎn)足x1≤x2≤…≤xm，通過(guò)上文論述，m邊形的結(jié)構(gòu)(x1,x2，…，xm)循環(huán)左移時(shí)會(huì)產(chǎn)生m種等價(jià)結(jié)構(gòu)（如表5所示），例如m邊形的結(jié)構(gòu)循環(huán)向左移動(dòng)1個(gè)單位，其結(jié)構(gòu)變?yōu)?x2,x3，…，xm,x1)，若它也滿(mǎn)足m邊形的標(biāo)準(zhǔn)結(jié)構(gòu)的約束條件則有：x2≤x3≤…≤xm≤x1，于是整體約束需要同時(shí)滿(mǎn)足 x1≤x2≤…≤xm和 x2≤x3≤…≤xm≤x1，得到 xm=x1。 當(dāng) m 邊形結(jié)構(gòu)(x1,x2，…，xm)循環(huán)左移 k（0＜k＜m）個(gè)單位后，若其結(jié)構(gòu)也滿(mǎn)足標(biāo)準(zhǔn)結(jié)構(gòu)則有xm=x1=x2…=xk，在求解m邊形結(jié)構(gòu)的過(guò)程中，是要排除等價(jià)結(jié)構(gòu)的，從而令x1＜xm就可以排除等價(jià)結(jié)構(gòu)，于是求解第二類(lèi)m邊形時(shí)有約束：

m邊形的不同結(jié)構(gòu)的數(shù)量為S1∪S2，舉一個(gè)例子來(lái)說(shuō)明。當(dāng)n=14，求在n=14等分圓上3邊形的結(jié)構(gòu)，n=14，則有 1，2，3， …，7 個(gè)弧長(zhǎng)，3 邊形的結(jié)構(gòu)可以表示為(x1,x2,x3)，有：

求解S1和S2得到的3邊形的不同結(jié)構(gòu)見(jiàn)表8所示，第一類(lèi)3邊形為15個(gè)，第二類(lèi)3邊形為 11個(gè)，3邊形的不同結(jié)構(gòu)一共有26個(gè)。

表8 3邊形的不同結(jié)構(gòu)

5 m邊形的奇偶屬性

若m與n沒(méi)有公因子，m邊形沿著圓周轉(zhuǎn)動(dòng)可以產(chǎn)生n個(gè)不同的m邊形，這n個(gè)m邊形根據(jù)奇偶屬性可分為2類(lèi)，在同一個(gè)類(lèi)里，所有m邊形的奇偶屬性相同。

m邊形的奇偶屬性為m邊形中m個(gè)數(shù)字的奇偶性，例如當(dāng)n=14，m=3時(shí)，3邊形123可產(chǎn)生14個(gè)3邊形，這14個(gè)3邊形可分為2類(lèi)，如表9所示，在第一類(lèi)里所有3邊形的奇偶屬性為(奇,偶,奇)；在第二類(lèi)里所有3邊形的奇偶屬性為(偶,奇,偶)。

表9 3邊形123的奇偶屬性

在n等分圓周上，可以通過(guò)上述求解約束方程來(lái)求解m邊形的不同結(jié)構(gòu)，同時(shí)已知m邊形的結(jié)構(gòu)也可以求m邊形的初始化值，根據(jù)奇偶屬性，對(duì)于每個(gè)m邊形結(jié)構(gòu)，有兩種初始化值。若已知m邊形的結(jié)構(gòu)為(x1,x2,x3,…xm)，則對(duì)應(yīng)的m邊形為y1,y2,y3,…,ym。

第一類(lèi)初始化值為：yi+1=yi+xi,1≤i＜m，y1=1

第二類(lèi)初始化值為：yi+1)=yi+xi,1≤i＜m，y1=2

當(dāng)n=14時(shí)，不同結(jié)構(gòu)的3邊形的初始化值如表10～11所示。

表10 n=14時(shí)3邊形的第一類(lèi)初始化值

表11 n=14時(shí)3邊形的第二類(lèi)初始化值

6 在科克曼三元系中的應(yīng)用

圖2 n=14等分圓

由上文可知，n=14，m=3時(shí)，有26個(gè)不同結(jié)構(gòu)的3邊形，在n=14的等分圓周上圓周3邊形的數(shù)量為26×14=364，恰好等于。圓心3邊形為圓心15與圓周上的2個(gè)元素的組合，其3邊形結(jié)構(gòu)用(L,R,R)表示，其中L為n=14等分圓周上的2個(gè)元素的弧長(zhǎng)，R表示半徑；當(dāng)n=14時(shí)，如圖2所示，其基本弧長(zhǎng)有：1,2,3，…，7，其中弧長(zhǎng)等于7的2邊形只能循環(huán)產(chǎn)生7個(gè)不同2邊形，那么對(duì)應(yīng)的不同圓心3邊形也只有7個(gè)，如表12所示；其他的弧長(zhǎng)對(duì)應(yīng)2邊形都可生成14個(gè)不同的2邊形，其對(duì)應(yīng)的圓心3邊形也有14個(gè)，所以圓心3邊形的總數(shù)為：14×6+7=91，恰好等于。 n=14，其圓心3邊形的結(jié)構(gòu)和初始化值如表13所示。

表12 弧長(zhǎng)7生成的2邊形和圓心3邊形

表13 n=14圓心3邊形及結(jié)構(gòu)

柯克曼三元系的一個(gè)平行類(lèi)可以表示為圓上的點(diǎn)（包括圓心）組成的3邊形，如圖3所示，有柯克曼三元系的平行類(lèi)：1-2-15,4-5-8,7-11-13,10-12-3,6-9-14。這5個(gè)3邊形，每次循環(huán)轉(zhuǎn)動(dòng)2個(gè)單位，可以生成一個(gè)有效柯克曼三元系，如表14所示。

圖3 柯克曼三元系的平行類(lèi)

表14 一個(gè)柯克曼三元系的構(gòu)造

從表14可知，每個(gè)平行類(lèi)的5個(gè)3邊形的結(jié)構(gòu)都是相同的，所以要用組合的循環(huán)生成法生成柯克曼三元系的首要任務(wù)就是找到有效的3邊形結(jié)構(gòu)序列，例如找到一個(gè)有效的3邊形結(jié)構(gòu)序列：(1,R,R),(1,3,4),(4,2,6),(2,5,7),(3,5,6)。

怎么樣的3邊形結(jié)構(gòu)序列才是有效的呢？用圓周3邊形和圓心3邊形構(gòu)造KTS(15)的一個(gè)平行類(lèi)，KTS(15)中有一個(gè)三元系包含數(shù)字15，所以KTS(15)的一個(gè)平行類(lèi)包含1個(gè)圓心3邊形和4個(gè)圓周3邊形，圓心3邊形有一個(gè)有效弧長(zhǎng)，圓周3邊形有3個(gè)有效弧長(zhǎng)，則一個(gè)平行類(lèi)的總弧長(zhǎng)數(shù)量為1+3×4=13，那么若要用圓心3邊形和圓周3邊形表示柯克曼三元系，其弧長(zhǎng)應(yīng)該怎么分配呢？

結(jié)論是：弧長(zhǎng)1,2,3…6在3邊形結(jié)構(gòu)序列中使用兩次，且對(duì)于每個(gè)弧長(zhǎng)，兩次使用產(chǎn)生的2邊形分別屬于不同奇偶屬性，弧長(zhǎng)7使用一次時(shí)，可滿(mǎn)足生成柯克曼三元系KTS(15)的條件。

原因?yàn)椋趎=14的等分圓周上一共有7個(gè)基本弧長(zhǎng)，弧長(zhǎng)1,2,3，…，6可循環(huán)產(chǎn)生14個(gè)不同2邊形，因?yàn)镵TS(15)有7個(gè)平行類(lèi)，所以弧長(zhǎng)1,2,3，…，6在3邊形結(jié)構(gòu)序列中可以使用兩次，又因?yàn)樵贙TS(15)的35個(gè)三元系中，任意兩個(gè)數(shù)字只能結(jié)合一次，所以對(duì)于弧長(zhǎng)1,2,3，…，6，每次使用時(shí)產(chǎn)生的2邊形必須分別為不同奇偶屬性，例如對(duì)于表14的結(jié)構(gòu)序列，(1,R,R)和(1,3,4)都使用了弧長(zhǎng) 1，弧長(zhǎng)1 在(1,R,R)和(1,3,4)中對(duì)應(yīng)的2邊形如表15所示，分別為不同的奇偶屬性。而對(duì)于弧長(zhǎng)7，只能循環(huán)產(chǎn)生7個(gè)2邊形，所以弧長(zhǎng)7只能使用一次。

表15 弧長(zhǎng)1在不同結(jié)構(gòu)里對(duì)應(yīng)的2邊形

對(duì)于n=14,滿(mǎn)足柯克曼三元系的結(jié)構(gòu)序列如附件1所示。

1.在附件1中取出一個(gè)3邊形結(jié)構(gòu)序列，例如第8個(gè)：(1,R,R),(1,3,4),(4,2,6),(2,5,7),(3,5,6)

2.對(duì)于上述3邊形結(jié)構(gòu)序列中的圓心3邊形的初始化是固定，根據(jù)表13直接初始化；對(duì)于圓周3邊形，有兩種初始化形式，根據(jù)柯克曼三元系的約束條件，選擇對(duì)應(yīng)的初始化值，使得弧長(zhǎng)1,2,3，…，6所對(duì)應(yīng)的兩個(gè)線(xiàn)段為不同奇偶屬性。

例如，對(duì)于上述3邊形結(jié)構(gòu)序列有：

1）對(duì)于弧長(zhǎng)1，出現(xiàn)在(1,R,R)和(1,3,4)中，圓心3邊形直接初始化，(1,R,R)的3邊形初始化為1 2-15，于是弧長(zhǎng)1對(duì)應(yīng)的線(xiàn)段為1-2；對(duì)(1,3,4)進(jìn)行初始化時(shí)，弧長(zhǎng)1對(duì)應(yīng)的線(xiàn)段必須和1-2(1)為不同奇偶屬性，所以(1,3,4)的初始化3邊形為2-3-6；

2）對(duì)于弧長(zhǎng)3，出現(xiàn)在(1,3,4)和(3,5,6)中，在(1,3,4)中對(duì)應(yīng)的線(xiàn)段為3-6，對(duì)(3,5,6)進(jìn)行初始化時(shí)，弧長(zhǎng)3對(duì)應(yīng)的線(xiàn)段必須和36(3)為不同奇偶屬性，所以(3,5,6)的初始化3邊形為2-5-10；

3）對(duì)于弧長(zhǎng)4，出現(xiàn)在(1,3,4)和(4,2,6)中，在(1,3,4)中對(duì)應(yīng)的線(xiàn)段為2-6，對(duì)(4,2,6)進(jìn)行初始化時(shí)，弧長(zhǎng)4對(duì)應(yīng)的線(xiàn)段必須和2-6(4)為不同奇偶屬性，所以(4,2,6)的初始化3邊形為1-5-7；

4）對(duì)于弧長(zhǎng)2，出現(xiàn)在(4,2,6)和(2,5,7)中，在(4,2,6)中對(duì)應(yīng)的線(xiàn)段為5-7，對(duì)(2,5,7)進(jìn)行初始化時(shí)，弧長(zhǎng)2對(duì)應(yīng)的線(xiàn)段必須和5-7(2)為不同奇偶屬性，所以(2,5,7)的初始化3邊形為2-4-9；

5）對(duì)于弧長(zhǎng) 5，出現(xiàn)在(3,5,6)和(2,5,7)中，(3,5,6)已初始化為 2-5-10，(2,5,7)已初始化為 2-4-9，弧長(zhǎng) 5在(3,5,6)對(duì)應(yīng)的線(xiàn)段為5-10，在(2,5,7)對(duì)應(yīng)的線(xiàn)段為49，弧長(zhǎng)5對(duì)應(yīng)的兩條線(xiàn)段有不同的奇偶屬性。

6）對(duì)于弧長(zhǎng) 6，出現(xiàn)在(3,5,6)和(4,2,6)中，(3,5,6)已初始化為 2-5-10，(4,2,6)已初始化為 1-5-7，弧長(zhǎng) 6在(3,5,6)對(duì)應(yīng)的線(xiàn)段為2-10，在(4,2,6)對(duì)應(yīng)的線(xiàn)段為1-7，弧長(zhǎng)6對(duì)應(yīng)的兩條線(xiàn)段有不同的奇偶屬性。通過(guò)上面的分析得到3邊形結(jié)構(gòu)序列的初始化值，如表16所示。

表16 3邊形結(jié)構(gòu)序列的初始化值

3.要滿(mǎn)足柯克曼三元系每個(gè)平行類(lèi)必須包含1到15的數(shù)字，令圓心3邊形的初始化值1-2-15不變，4個(gè)圓周3邊形循環(huán)加2，得到一個(gè)2維數(shù)組，如表17所示，然后在數(shù)組里搜索滿(mǎn)足柯克曼三元系一個(gè)平行類(lèi)（帶底紋），最后得到3邊形結(jié)構(gòu)序列的初始化值，如表18所示。

表17 圓周3邊形生成的2維數(shù)組

表18 柯克曼三元系的一個(gè)平行類(lèi)

對(duì)表18中的3邊形循環(huán)轉(zhuǎn)動(dòng)2個(gè)單位生成柯克曼三元系，如表14所示。

7 結(jié)論

在本文中，從計(jì)算機(jī)科學(xué)的角度提出了一種遞歸構(gòu)造柯克曼三元系的新方法，將集合V中{1,2,3,...,v}中的元素對(duì)應(yīng)在等分圓上，一個(gè)柯克曼平行類(lèi)可以由圓上的區(qū)塊（三角形）表示。我們給出構(gòu)造KTS(v)的第一并行類(lèi)的約束，以及如何構(gòu)造KTS(v)的第一并行類(lèi)，通過(guò)固定點(diǎn)v并沿著圓周上循環(huán)轉(zhuǎn)動(dòng)2個(gè)單位可以得到柯克曼三元系的構(gòu)造。當(dāng)v=15時(shí)，依照上述組合循環(huán)生成法的步驟寫(xiě)程序運(yùn)行可獲得44個(gè)解。盡管已經(jīng)存在構(gòu)造KTS(v)的傳統(tǒng)方法，但是以上提供的方法是可針對(duì)v≡3 mod 12遞歸構(gòu)造柯克曼三元系，研究結(jié)果將為遞歸構(gòu)造柯克曼三元系提供新的思路和方法。