前言

之前做了一個四國軍棋軟件，做到最后發現工作量已經爆炸了，我需要去尋找一個全新的算法來減少工作量，所謂深度學習的算法也許有效果但是對于沒有計算資源的人來說并不適用。

我其實是挺喜歡數學的，我總覺得數學上的一些思想方法可能對寫代碼有所幫助，但是我已經深深意識到自己的大腦不適合去處理數學問題。數學的語言是精確的，數學書籍的作者想表達的意思也是清晰的，對于高智商的人能很容易明白作者的意思，但是對于我這么一個智商一般的人來說，經常感覺到作者想表達的實際意思和自己理解的意思不一樣，讀起來相當痛苦。另外對于一些高深的數學概念，往往是由很多基礎的數學概念疊加而成的，這就需要良好的記憶力，在讀到后面時能夠十分清楚的記住之前講述的概念。而我的記憶力很差，當后面定義的新概念需要依賴之前的概念，而我經常忘記之前的概念，甚至草草在腦中代入一個錯誤的概念，這樣接下來讀起來就會不知所云。

用C語言去描述數學可能可以解決我閱讀數學時的困境，如果代碼表達的實際意義和我理解的有偏差，我只需要debug一下，去追蹤到底代碼哪一行跟自己的理解不一樣，從而糾正自己錯誤的理解。另外一些概念是由很多其他概念組成的，在C語言中這些概念可以理解成函數，借助eclipse這樣的開發環境，對于我不理解的概念，我可以跳轉到這個函數中再來仔細研究，也可以很快的知道各種概念之間的區別和聯系，只要比較對應代碼的形式和運行結果就可以知道了。

為了處理的簡單和方便，這里會忽略掉一些數學上的嚴謹性，也不是很注重軟件工程的設計，目的主要是提取數學的思想，把一些抽象的概念實例化，從而能更好的理解數學的結構，使數學概念能夠通過清晰的代碼步驟表現出來。我打算研究抽象代數、組合數學、數理邏輯這三方面的內容，先從抽象代數開始。參考的教材是E.Artin的《伽羅華理論》，再隨便配上一本抽象代數或近世代數的書。

1 置換群

群是代數中最基本的概念，而置換群是一種最基本的群，群的概念就是從置換中誕生的，所以先來研究置換群。

1.1 置換

先來定義置換的概念，這里不用數學語言來精確定義，只舉實際例子把這個概念說的相對明白就可以了。

現在有一個5元排列（1 2 3 4 5），我們把這排列中的5個元素隨便調換一下順序就可以得到另外一個排列了，比如把2和4交換，1和3交換得到另一個排列（3,4,1,2,5），我們可以把置換用映射表示

$$f=?\begin{array}{rl}1\to & 3\\ 2\to & 4\\ 3\to & 1\\ 4\to & 2\\ 5\to & 5\end{array}$$
簡記為
$$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 4& 1& 2& 5\end{array}\right)$$

還有一種更簡單的記法，例如把（1 2 3 4 5）的這個排列的每個元素都向左移動一個位置得到置換
$$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 3& 4& 5& 1\end{array}\right)$$
這種置換稱作輪換，反復映射后可以得到1->2->3->4->5->1,可以直接用輪換中的任一個排列表示即（1 2 3 4 5）
每一個置換都可以表示成一些輪換的組合，例如
$$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 4& 1& 2& 5\end{array}\right)$$
可以表示為(1 3)(2 4)(5),即1和3輪換，2和4輪換，5不變，尋找輪換的方法是:
1->3->1,2->4->2,從起始位置開始反復映射，回到自身就是一個輪換。

1.2 群

群是由一個集合中的元素比如集合A={a,b,c,d…}和運算{$?$}組成的，要注意的是集合中的元素不一定是數字，運算也不一定是乘法，集合和運算具體代表什么需要你自己定義。這些元素的運算必須滿足下面4個條件才能稱作群

運算封閉，即$a?b$的結果仍在A中

結合律，即$(a?b)?c=a?(b?c)$

有單位元e，即 對于任意的a，存在單位元e使得 $e?a=a$

有左逆元，即對于任意的a，存在b滿足$b?a=e$,那么b叫做a的左逆元

一般來說群并沒有規定運算要滿足交換律，下面來說明上面定義的置換是群，首先定義置換的運算{$?$}如下，例如（1 2 3 4 5）$?$ (1 3)(2 4)(5)的計算結果如下

即
$$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 3& 4& 5& 1\end{array}\right)?\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 4& 1& 2& 5\end{array}\right)=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 4& 5& 2& 3& 1\end{array}\right)$$

接下來將用代碼證明置換滿足群的4條性質，證明第1條性質時需要對置換的概念做一些額外的說明，并寫一個函數判斷這個元素是不是置換，這個性質是顯然滿足的，并且寫成代碼并不會更加清晰所以略去，所以主要證明的是第2,3,4條性質

2 代碼實現

2.1 數據結構

首先需要定義一個代數系統的數據結構，初步定義如下

typedef struct OperateSys OperateSys; struct OperateSys {void *pBaseEle;//單位元int (*xIsEqual)(void *, void *);//判斷2個元素是否相等void *(*xGen)(int iNum);//根據給定的自然數生成集合中的元void *(*xInvEle)(void *);//給定一個元素生成逆元void *(*xRecursiveGen)(void *pEle);//根據一個元素遞歸生成下一個元素，暫時不用void *(*xOperat)(void *, void *);//運算void *(*xConjOperat)(void *, void *);//共軛運算，這個運算下面會特別說明 };

在實現置換群的代數系統時，首先要定義置換元素的結構

typedef struct FivePerm {u8 aNum[5]; }FivePerm;

下面來新建一個置換群的OperateSys的對象

OperateSys *PermutationObj(void) {//1->1,2->2,3->3,4->4,5->5作為單位元static FivePerm baseItem ={.aNum[0] = 1,.aNum[1] = 2,.aNum[2] = 3,.aNum[3] = 4,.aNum[4] = 5,};//函數類型不匹配，加void去警告static OperateSys perm ={NULL,(void*)FivePermEqual,(void*)FivePermGen,(void*)FivePermInv,(void*)FivePermRec,(void*)FivePermOp,(void*)FivePermOp1,};perm.pBaseEle = &baseItem;return &perm; }

2.2 置換生成

置換是一個集合，為了實現這個代數運算系統，我們首先要生成置換的所有元素，以5個元素的置換為例，這些元素就是(1 2 3 4 5)的一個全排列，全排列總共有120個，所以輸入范圍從0~119，生成算法采用的是遞歸的思想，第1個數字可能的取值為1,2,3,4,5五種，確定第1個數字之后，下面進行遞歸調用求得剩下4個數字的全排列

//pPerm為初始輸入元素,即恒等置換(1) //left表示置換中最左邊的一個元素， //right表示置換中最右邊的一個元素 //要生成的元素的序號 void FivePermTrav(FivePerm *pPerm, int left, int right, int num) {static int cnt = 0;static int RecCnt = 0;int i;//cnt是靜態變量，第一次調用遞歸時先清0if( RecCnt==0 ){cnt = 0;}RecCnt++;//找到要生成的元素后返回if( cnt>num ){RecCnt--;return;}//遞歸結束，找到一個置換if( left==right ){cnt++;}else{//把子置換中最左邊的元素依次與右邊每個元素調換繼續遞歸for(i=left; i<=right; i++){SwapNum(&pPerm->aNum[i],&pPerm->aNum[left]);FivePermTrav(pPerm,left+1,right,num);// 已經找到要求得元素就不要繼續遞歸了if( cnt>num ){break;}//遞歸完畢后返回將元素換回來，保持初始狀態不變SwapNum(&pPerm->aNum[i],&pPerm->aNum[left]);}}RecCnt--; }// FivePerm *FivePermGen(int num) {FivePerm *p;u8 aInit[5] = {1,2,3,4,5};num = num%120;p = malloc(sizeof(FivePerm));memcpy(p->aNum,aInit,sizeof(aInit));FivePermTrav(p,0,4,num);return p; }

2.3 置換乘法運算

首先來實現1.2節定義的置換乘法運算,這是一個映射運算，只要把第2個輸入映射的結果作為第1個參數的下標得到運算結果即可:

FivePerm *FivePermOp(FivePerm *p1, FivePerm *p2) {FivePerm *p;int i,j;p = malloc(sizeof(FivePerm));memset(p,0,sizeof(FivePerm));for(i=0; i<5; i++){j = p2->aNum[i]-1;//獲取p2的映射結果p->aNum[i] = p1->aNum[j];//將j作為p1的下標 }return p; }

對于置換集合可以再定義一個共軛運算{$°$}，我們來計算 (1 3)(2 4)(5) $°$（1 2 3 4 5），其運算結果如下，先寫出右元的置換，再把左元寫成輪換形式，右元的結果根據左元進行輪換

這里我們發現以下等式成立，記為公式(1)
$$\begin{array}{rl}& \left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 3& 4& 5& 1\end{array}\right)?\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 4& 1& 2& 5\end{array}\right)\\ =& \left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 4& 1& 2& 5\end{array}\right)°\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 3& 4& 5& 1\end{array}\right)\\ =& \left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 4& 5& 2& 3& 1\end{array}\right)\end{array}\text{\hspace{1em}(1)}$$
即置換的乘法運算與其2個元素交換后的共軛運算是相等的，那么為什么會相等呢，我們先用代碼來實現共軛運算，上面舉的例子容易搞混，我再舉一個典型的例子，

按照上圖得到代碼的具體實現

FivePerm *FivePermOp1(FivePerm *p1, FivePerm *p2) {FivePerm *p;int i,j;p = malloc(sizeof(FivePerm));memset(p,0,sizeof(FivePerm));for(i=0; i<5; i++){//這里我們要對p2的元素進行置換//p2的哪個元素會換到i的位置上//根據p1的映射結果就可以得到要置換的位置//注意到p2是根據p1的輪換表示來置換的j = p1->aNum[i]-1;p->aNum[i] = p2->aNum[j];}return p; }

對比FivePermOp和FivePermOp1的代碼可以看到形式是完全一樣的，只不過p1和p2調換個位置，所以我們看到公式（1）是成立的

2.4 置換群的逆運算

以下代碼是求左逆元的算法，你可以嘗試寫寫求右逆元的代碼，你會發現和求左逆元的代碼一模一樣，這也就證明了群的左逆元必定是右逆元

FivePerm *FivePermInv(FivePerm *p1) {FivePerm *p;int i,j;p = malloc(sizeof(FivePerm));memset(p,0,sizeof(FivePerm));//無論是求左逆元還是右逆元在代碼上的形式是相同的for(i=0; i<5; i++){j = p1->aNum[i];p->aNum[j-1] = i+1;}return p; }

2.5 群的證明

下面證明群的三個性質，這里并非嚴格按照數學證明，而是我們本身就承認這些性質，通過構造測試用例來明白為什么這些性質是成立的。

結合律

int AssociativeLaw(OperateSys *pOpSys) {int rc = 0;int i,j,k;void* pT[7];for(i=0; i<10; i++){//隨機生成三個偽隨機數，并生成3個置換元pT[0]、pT[1]、pT[2]for(j=0; j<3; j++){k = FakeRand(i+j*10);pT[j] = pOpSys->xGen(k);}//證明(pT[0]*pT[1])*pT[2]=pT[0]*(pT[1]*pT[2])pT[3] = pOpSys->xOperat(pT[1],pT[2]);pT[4] = pOpSys->xOperat(pT[0],pT[1]);pT[5] = pOpSys->xOperat(pT[0],pT[3]);pT[6] = pOpSys->xOperat(pT[4],pT[2]);rc = pOpSys->xIsEqual(pT[5],pT[6]);for(j=0; j<7; j++){free(pT[j]);}assert( rc );}loga("associative ok");return rc; }

有單位元

int HasIdentityEle(OperateSys *pOpSys) {int rc = 0;int i,k;void* pEle;void* pGen;//隨機生成10個置換元for(i=0; i<10; i++){k = FakeRand(i);pGen = pOpSys->xGen(k);pEle = pOpSys->xOperat(pOpSys->pBaseEle,pGen);//證明單位元和群中的任一元相乘仍然等于該元rc = pOpSys->xIsEqual(pGen,pEle);free(pGen);free(pEle);assert( rc );}loga("identity ok %d",rc);return rc; }

存在可逆元

int HasInvEle(OperateSys *pOpSys) {int rc = 0;int i,k;void* pEle;void* pGen;void* pInv;for(i=0; i<10; i++){k = FakeRand(i+2);pGen = pOpSys->xGen(k);//隨機生成10個元并根據pOpSys->xInvEle生成 pInvpInv = pOpSys->xInvEle(pGen);//證明pInv就是可逆元pEle = pOpSys->xOperat(pGen,pInv);rc = pOpSys->xIsEqual(pOpSys->pBaseEle,pEle);free(pGen);free(pEle);free(pInv);assert( rc );}loga("inv ok %d",rc);return rc; }

3參考代碼

https://github.com/pfysw/CMath

總結

以上是生活随笔為你收集整理的抽象代数的代码实现（1） 置换群的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。