版權(quán)申明：本文為博主窗戶(Colin Cai)原創(chuàng)，歡迎轉(zhuǎn)帖。如要轉(zhuǎn)貼，必須注明原文網(wǎng)址

　　 http://www.rzrgm.cn/Colin-Cai/p/18774816.html

　　作者：窗戶

　　QQ/微信：6679072

　　E-mail：6679072@qq.com

我準(zhǔn)備講有限Abel群，總覺(jué)得，對(duì)于一個(gè)程序員來(lái)說(shuō)，離散數(shù)學(xué)的各個(gè)科目無(wú)論是從訓(xùn)練思維還是從實(shí)用角度都是不錯(cuò)的。總是覺(jué)得程序員應(yīng)該重視理論方面的學(xué)習(xí)，其中自然也包括數(shù)學(xué)。當(dāng)然，講解過(guò)程中也包含著一些程序，畢竟程序才是程序員的根。

映射

序偶(pair)，是把兩個(gè)東西綁在一起，我們可以記為$<a, b>$

我們可以定義$<a,b>=\{\{a\},\{a,b\}\}$

為何這樣定義，就表示a/b的有序性了，自己想想，注意，按照以上定義，

$<a,a>=\{\{a\}\}$

當(dāng)然，你可以用別的定義方法，只要能保證唯一性。

集合$A$和集合$B$的笛卡爾積(Cartesian Product)，定義如下：

$A\times B=\{<a,b>|a\in A,b\in B\}$

也就是遍歷$A$的元素和$B$的元素組成序偶的所有可能。

比如$\{1,2\}$和$\{a,b,c\}$的笛卡爾積是$\{<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>\}$

映射(mapping)，又叫函數(shù)(function)，這個(gè)概念為大家所熟知，此處還是得形式化描述一下

集合$A$到集合$B$的映射$f$，是指$A\times B$的子集，滿足

 $\forall a\in A \exists!b\in B:<a,b>\in f$

換成大白話，就是對(duì)于任意$A$里的元素$a$，$f(a)$都是$B$里的元素，存在且唯一。

其中，$A$是$f$的定義域，$B$是$f$的值域。

半群

后面，我們看一種特殊的函數(shù)，對(duì)于集合$A$,

它的定義域是$A\times A$，值域?yàn)?A$

這種函數(shù)我們稱為集合$A$上的二元運(yùn)算，比如我們常見(jiàn)的加法、減法、乘法、除法(當(dāng)然，無(wú)論是對(duì)于整數(shù)集、有理數(shù)集、實(shí)數(shù)集、復(fù)數(shù)集)......

如果集合$A$上的二元運(yùn)算$f$滿足結(jié)合律，也就是

$\forall a,b,c\in A:f(<<a,b>,c>) = f(<a,<b,c>>)$

則稱集合$A$在二元運(yùn)算$f$下構(gòu)成一個(gè)半群(semigroup)

這樣寫(xiě)，不是我們習(xí)慣的寫(xiě)法，我們一般把滿足結(jié)合律的二元運(yùn)算叫乘法，用中綴表達(dá)式更習(xí)慣，那么乘法滿足交換律，則為

$\forall a,b,c\in A:(a\cdot b)\cdot c=a\cdot (b\cdot c)$

現(xiàn)實(shí)中很多這樣的半群例子，比如整數(shù)集在乘法下構(gòu)成半群，非0整數(shù)集在乘法下構(gòu)成半群。

再比如2階實(shí)數(shù)矩陣集在矩陣乘法下構(gòu)成半群。

當(dāng)然，整數(shù)在加法下也構(gòu)成半群，但可能會(huì)有點(diǎn)困惑，加法、乘法......

實(shí)際上，數(shù)學(xué)上，要注意的是形式的不變性，至于叫什么，不重要，真不重要。

群

如果一個(gè)半群滿足以下兩點(diǎn)：

(1) 該半群里有一個(gè)元$e$，對(duì)于半群里任何元$x$，都有

      $x=x\cdot e=e\cdot x$

(2)對(duì)于半群里任意一個(gè)元$x$，都存在一個(gè)$x'$，使得

      $x\cdot x' = x' \cdot x = e$

那么，我們稱這個(gè)半群為群(group)。

其中，滿足第一個(gè)條件的$e$為該群的幺元，或稱單位元；第二個(gè)條件里的$x$和$x'$互為逆元。

舉幾個(gè)實(shí)際的群的例子：

實(shí)數(shù)集在加法上為一個(gè)群，其中幺元是0(任何數(shù)加上0值不變)，每個(gè)元的逆元是其相反數(shù)(任何數(shù)和其相反數(shù)相加等于0)；

非零實(shí)數(shù)集在乘法上為一個(gè)群，其中幺元是1(任何數(shù)乘以1值不變)，每個(gè)元的逆元是其倒數(shù)(任何數(shù)和其倒數(shù)相等于1)，此處注意實(shí)數(shù)集在乘法上并不是一個(gè)群，因?yàn)?不存在逆元;

對(duì)于一個(gè)具體的正整數(shù)n，實(shí)數(shù)n階非奇異矩陣(也就是行列式值不為0)構(gòu)成的集合在矩陣乘法上為一個(gè)群，其中幺元是$I_{n}$，每個(gè)元的逆元是其逆陣。

群里元素的數(shù)量叫做群的階。

相同階的群

本節(jié)是想寫(xiě)程序看看給定階數(shù)的群有哪些。

作為抽象代數(shù)的重要分支，群論不是簡(jiǎn)單幾句就可以說(shuō)清楚的，本系列其實(shí)也只會(huì)講群論的一小部分。所以本節(jié)主要是暴力求解。

我們想暴力求給定n階群(也就是群里元素的個(gè)數(shù)為n)的群有哪些，那么我們?cè)O(shè)這些元素為$S_0,S_1,...S_{n-1}$，在不引起誤解的時(shí)候，我們可以用$0,1,...S_{n-1}$來(lái)代表$S_0,S_1,...S_{n-1}$，嗯，都到了抽象代數(shù)這樣的程度，其實(shí)符號(hào)未必重要。

我們用一個(gè)$n\times n$的方陣$A$來(lái)代表這個(gè)群，其實(shí)也就是這個(gè)群上的乘法表，其中

$S_a\cdot S_b = S_{A_{a,b}}$

我們就用Python來(lái)實(shí)現(xiàn)吧，就用自帶的array庫(kù)用一維數(shù)組${B}$來(lái)模擬方陣吧。

$A_{a,b} = B_{a*n+b}$

先建立高階的暴力求解框架，如下：

def make_search_all_groups_func(get_all_maybe_groups, is_group, print_group):
    def f(n):
        for s in get_all_maybe_groups(n):
            if is_group(n, s):
                print_group(n, s)
    return f

get_all_maybe_groups是用來(lái)產(chǎn)生可能是group的二元運(yùn)算，因?yàn)榇x對(duì)象可能很多，gen_all_maybe_groups一般應(yīng)該是個(gè)generator。

is_group是用來(lái)判定這個(gè)二元運(yùn)算是不是可以作為群的乘法表，

如果是，就打印出這個(gè)群，當(dāng)然，這個(gè)群可以用乘法表來(lái)代表。

那么，這個(gè)打印群，我們可以這樣寫(xiě):

def print_group(n, s):
    a = 0
    b = 0
    print('group:')
    for r in s:
        print('S%d x S%d = S%d' % (a, b, r))
        if b < n - 1:
            b += 1
        else:
            a += 1
            b = 0
    print('', end='', flush=True)

以上不難，那么接下來(lái)的問(wèn)題在于如何遍歷所有可能的二元運(yùn)算，簡(jiǎn)單的想想，這應(yīng)該是$n\times n$個(gè)$\{0,1...n-1\}$來(lái)做笛卡爾積，

好在Python有itertools庫(kù)可以做笛卡爾積，

itertools.product(range(n), range(n) ...)

可惜是個(gè)不固定參數(shù)的調(diào)用，不過(guò)Python是可以支持的，支持的方法就是這個(gè)*，展開(kāi)參數(shù)，很像Lisp的apply函數(shù)。

import array
import itertools as it
def get_all_maybe_groups_v1(n):
    return map(lambda s:array.array('i', s), it.product(*[range(n)]*(n**2)))

前面加個(gè)map將每個(gè)元素轉(zhuǎn)為array，之所以變成array，在于array尋址效率高。

然后就是判定是否為群了，判定是否為群，需要經(jīng)過(guò)三步：

(1)判斷二元運(yùn)算是否滿足結(jié)合律

(2)判斷是否有幺元

(3)判斷是否每個(gè)元都有逆元

那么寫(xiě)成代碼可以如下：

def is_group_v1(n, s):
    if not assoc_low(n, s): #結(jié)合律檢驗(yàn)
        return False
    e = get_ident_element(n, s) #找幺元
    if e is None:
        return False
    if not each_can_inverse(n, s, e): #看是否每個(gè)元都有逆元
        return False
    return True

分別實(shí)現(xiàn)三個(gè)函數(shù)。

結(jié)合律也是笛卡爾積遍歷所有可能，分別檢驗(yàn)

def assoc_low(n, s):
    mul = lambda a, b : s[a * n + b] #乘法
    for a, b, c in it.product(range(n), range(n), range(n)):
        if mul(mul(a, b), c) != mul(a, mul(b, c)):
            return False
    return True

再來(lái)找幺元，看是否有一個(gè)元，所有元和它左乘右乘都不改變，

def get_ident_element(n, s):
    mul = lambda a, b : s[a * n + b] #乘法
    for i in range(n):
        flag = True
        for j in in range(n):
            if mul(i, j) != j or mul(j, i) != j:
                flag = False
                break
        if flag:
            return i
    return None

最后再來(lái)看每個(gè)元有沒(méi)有逆元，依然是遍歷，

def each_can_inverse(n, s, e):
    mul = lambda a, b : s[a * n + b] #乘法
    for i in range(n):
        flag = False
        for j in range(n):
            if mul(i, j) == e and mul(j, i) == e:
                flag = True #找到了逆元，標(biāo)記一下找到了
                break
        if not flag:
            return False #當(dāng)前i沒(méi)有找到逆元
    return True

這樣，我們實(shí)現(xiàn)了一個(gè)搜索版本

search_all_groups_v1 = make_search_all_groups_func(get_all_maybe_groups_v1, is_group_v1, print_group)

結(jié)果我們調(diào)用search_all_groups_v1(4)希望搜索4階群，就發(fā)現(xiàn)計(jì)算非常慢了。

我們是不是可以再快一點(diǎn)呢？

很多時(shí)候，此類搜索我們發(fā)現(xiàn)一些定理就可以加快搜索速度。

我們先證明一個(gè)命題:

對(duì)于任意群$<G,\cdot>$，

$\forall a,b,c\in G:a\cdot b=a\cdot c \rightarrow b = c$

$\forall a,b,c\in G:b\cdot a=c\cdot a \rightarrow b = c$

其實(shí)，

 $a \cdot b = a \cdot c$
 $\rightarrow a^{-1}\cdot(a \cdot b) = a^{-1}\cdot(a \cdot c)$
 $\rightarrow (a^{-1}\cdot a) \cdot b = (a^{-1}\cdot a) \cdot c$
 $\rightarrow e \cdot b = e \cdot c$
 $\rightarrow b = c$
其中，$a^{-1}$是$a$的逆元，$e$是群的幺元。

同理，

$b \cdot a = c \cdot a$
$\rightarrow (b \cdot a) \cdot a^{-1} = (c \cdot a) \cdot a^{-1}$
$\rightarrow b \cdot (a \cdot a^{-1}) = c \cdot (a \cdot a^{-1})$
$\rightarrow b \cdot e = c \cdot e$
$\rightarrow b = c$

于是我們知道，對(duì)于群里的任何一個(gè)元素，乘以不同的元素得到的結(jié)果都不一樣，

那么再細(xì)細(xì)一想，對(duì)于群里任何一個(gè)元素$a$，乘以$S_{0},S_{1}...S_{n-1}$得到的$a \cdot S_{0}, a \cdot S_{1}...a \cdot S_{n-1}$是$S_0,S_1...S_{n-1}$的一個(gè)排列，

被$S_{0},S_{1}...S_{n-1}$乘得到的$S_0 \cdot a ,S_1 \cdot a ...S_{n-1} \cdot a $也是$S_0,S_1...S_{n-1}$的一個(gè)排列。

乘法表這樣一個(gè)矩陣?yán)锏拿總€(gè)數(shù)，其在所屬行和所屬列里是獨(dú)一無(wú)二的。

利用這個(gè)性質(zhì)，我們篩選二元運(yùn)算時(shí)，就可以不要用笛卡爾積了，這樣輕松的篩掉了絕大多數(shù)不可能是群乘法的二元運(yùn)算。

另外，我們可以一上來(lái)就讓$S_0$來(lái)做群的幺元，于是$n\times n$的乘法表已經(jīng)固定了其中的$2n-1$項(xiàng)，

def get_all_maybe_groups_v2(n):
    #0是幺元,先固定2n-1項(xiàng)
    arr = array.array('i', n * n * [0])
    for i in range(n):
        arr[i] = i
        arr[n * i] = i
    #從1行1列開(kāi)始遍歷
    row, col = 1, 1
    FORWARD, BACKWARD = True, False
    while True:
        #初始的時(shí)候,搜索的方向默認(rèn)為向后,只有成功找到了一個(gè)值才能改為向前
        direction = BACKWARD
        #依次從當(dāng)前值開(kāi)始搜索到最小的值,滿足行/列無(wú)重復(fù)
        for i in range(arr[row * n + col], n):
            flag = True
            for j in it.chain(range(row * n, row * n + col), range(col, row * n + col, n)):
                if arr[j] == i:
                    #行列上有重復(fù),就報(bào)錯(cuò)標(biāo)志置起來(lái)
                    flag = False
                    break
            if flag:
                #成功的找到了新值,flag設(shè)為真用來(lái)代表找到了
                direction = FORWARD
                arr[row * n + col] = i
                break
        if direction == FORWARD:
            #找到了當(dāng)前的值,那么可以繼續(xù)往前,坐標(biāo)往前進(jìn)一個(gè)
            col += 1
            if col >= n:
                col = 1
                row += 1
                if row == n:
                    #此時(shí),已經(jīng)滿了,得到了一個(gè)新的候選二元運(yùn)算
                    yield arr
                    #后退兩行加兩個(gè)元素
                    #為什么可以后退這么多來(lái),實(shí)際需要證明一下,有興趣就想想如何證明吧
                    #因?yàn)橹粍?dòng)最后兩行沒(méi)有其他可能解
                    #直覺(jué)能后退更多一點(diǎn),不過(guò)連我自己也沒(méi)多想
                    row = n - 3
                    col = n - 2
                    #既然是字典順序,當(dāng)前搜索的值至少要從下一個(gè)開(kāi)始
                    arr[row * n + col] += 1
                    #后面的其他值都清為0,這樣才是字典順序,不會(huì)漏掉候選者
                    arr[row * n + col + 1] = 0
                    for i in range((n - 2)*n+1, (n - 1)*n):
                        arr[i] = 0
                    for i in range((n - 1)*n+1, n*n):
                        arr[i] = 0
        else: #direction == BACKWARD
            #沒(méi)有找到當(dāng)前的值,只能坐標(biāo)往前退一步了
            #字典順序下,當(dāng)前值清為0,而退一步之后的位置則要加1,這才是緊接著的下一個(gè)字典序
            arr[row * n + col] = 0
            col -= 1
            if col == 0:
                col = n - 1
                row -= 1
                #退無(wú)可退,都退到第0行固定的那些值上去了,說(shuō)明遍歷完了
                if row == 0:
                    return
            arr[row * n + col] += 1