版權申明：本文為博主窗戶(Colin Cai)原創，歡迎轉帖。如要轉貼，必須注明原文網址 http://www.rzrgm.cn/Colin-Cai/p/18931900.html 作者：窗戶 QQ/微信：6679072 E-mail：6679072@qq.com
本節在上一節的結論基礎上，通過程序對于給定階數生成該階下所有可能的Abel群。
有限Abel群結構定理
我們再回憶一下有限Abel群的所有可能結構：
任何一個階數大于1的有限Abel群都可以同構為數個階數大于1的循環群的直積$Z_{a_1} \otimes Z_{a_2} \otimes ... \otimes Z_{a_n}$，并滿足各循環群的階數從左到右為約數關系，也就是$a_1|a_2|...|a_n$，另外$a_1,a_2,...,a_n$相乘等于原Abel群的階數。
另外，
如果$a_1,a_2,...,a_n$都是大于1的整數，$b_1,b_2,...,b_m$也都是大于1的整數,
$a_1|a_2|...|a_n$，并且$b_1|b_2|...|b_m$，
那么$Z_{a_1} \otimes Z_{a_2} \otimes ... \otimes Z_{a_n} \cong Z_{b_1} \otimes Z_{b_2} \otimes ... \otimes Z_{b_m}$
的充要條件是
$m=n \land a_1=b_1 \land a_2=b_2 \land ... \land a_n = b_n$
也就是只要有一個循環群不同，兩個Abel群就不同構。
比如$72$階Abel群，總共有以下幾個同構：
$Z_{72}$
$Z_2 \otimes Z_{36}$
$Z_3 \otimes Z_{24}$
$Z_6 \otimes Z_{12}$
$Z_2 \otimes Z_2 \otimes Z_{18}$
$Z_2 \otimes Z_6 \otimes Z_6$
以下，我們用程序實現，還是繼續選擇Python語言。
生成器遞歸實現
我們首先考慮生成器，我想程序員們大多對于此問題應該有遞歸的直覺。遞歸很多時候在于問題的分解。
Python的生成器其實是有點拗口的，它從語法上并非那么自然，使得像我這樣有點語法潔癖的人，總覺得有點疙瘩。
比如如下代碼：
def f(x): if x <= 0: return -x else: for i in range(x): yield i for i in f(10): print(i) print(f(-10))
它最后對于f(-10)的返回居然是<generator object f at 0x7f38ee923740>
Python對其解釋是，一日生成器終身生成器，也就是生成器和函數是不一樣的東西。好吧，唐僧取經最后都有幾卷經書曬在礁石上撕不下來，世間很難完美。
生成器中，部分流是從另外一個生成器中來的話，可以
for i in generator2(args):
yield i
不可以直接
generator2(args)
因為如此，Python會當成只是執行了一個函數。比較簡潔的寫法是
yield from generator2(args)
以上可以用于我們生成器的遞歸，而我們工作的核心在于如何分解任務。
其實，DC(分治)對一個問題可能有多種分解方式，這里我們就想一種最簡單明了的。
打個比方，我們來求$180$的所有可能。
那么，它可以是單獨的
$(180)$
也可能是
$(2 ...)$
也可能是
$(3 ...)$
也可能是
$(6 ...)$
注意，如果至少有兩個數，那么后面至少會有一個數，而且必須是前面數的倍數，也就是說，第一個數的平方必須是整體的約數，
$2^2|180$
$3^2|180$
$6^2|180$
當然，我們不用考慮$1$(這種平凡的Abel群我們可以當特例直接排除)的分解，那么，既然要考慮遞歸，就要更一般的考慮下去
假如我們已經把數字$N$分解到
$(a_1,a_2...a_n,...)$
當然，其中
$a_1|a_2...|a_n$
假設能分解到這步，也就是后面至少還有一項是$a_n$的倍數，從而
$(\prod_{i=1}^{i\le n}{a_i})*a_n|N$
也就是
$(a_1,a_2...a_n,\frac{N}{\prod_{i=1}^{i\le n}{a_i}})$
是后面僅剩一項的情況
如果
$\exists a_{n+1}:a_n|a_{n+1} \land (\prod_{i=1}^{i\le n}{a_i})*a_{n+1}^2|N$
那，我們可以繼續安插進下一項，這里找到的$a_{n+1}是合適的下一項，
$(a_1,a_2...a_n,a_{n+1}...)$
其實也就是，如果
$\exists m \in Z^+ : (m*a_n)^2|\frac{N}{\prod_{i=1}^{i\le n}{a_i}}$
那么是可以繼續安插進下一項，
$(a_1,a_2...a_n,a_{n+1}...)$
于是，我們先給定生成器用來生成$(a_1,a_2...,a_n)$開頭的所有的有效分解。
按照剛才的分析，生成器gen(remained, a)可以如下編寫，其中這里的remained則是剛才的$\frac{N}{\prod_{i=1}^{i\le n}{a_i}}$
def gen(remained, a): #自身是一個合理的分解 yield a + [remained] if a: #如果a里面有元素，那么挨個m*a[-1]遍歷試除一下 x = a[-1] while x * x <= remained: if remained % (x * x) == 0: yield from gen(remained // x, a + [x]) x += a[-1] else: #如果a是空列，那么挨個大于等于1的整數遍歷試除一下 x = 2 while x * x <= remained: if remained % (x * x) == 0: yield from gen(remained // x, a + [x]) x += 1
然后，最終的我們要的生成器，
gen_all_abel = lambda N:gen(N,[])
嗯，這里可以像函數一樣，lambda也是支持生成器的。
因式分解
考慮上面慢在哪里，找因子是依次這樣試除找過來，如果我們一早知道因式分解，應該是可以提升效率的。
因式分解就采用最簡單的試除如下：
def factor(N): ret = [] n = 2 while n * n <= N: if N % n == 0: k = 0 while N % n == 0: N //= n k += 1 ret.append((n, k)) n += 1 if N != 1: ret.append((N, 1)) return ret
所用算法沒啥大技巧，唯一要提的也就是和之前一樣，合數一定有一個約數小于等于自己的平方根。
有了這個之后，前面的算法可以先因式分解，然后再不需要依次試除，此處省略優化后的實現，由讀者自己去思考吧。
迭代器字序列實現
我們再來考慮迭代器序列的實現。
首先，我們意識到因式分解的好處，自然有很多計算基于因式分解。我們可以建立一個類來實現因式分解的運算。
class Factor(object): def __init__(self, arg=[]): if isinstance(arg, list): #傳入為因式分解list self.factor_list = arg elif isinstance(arg, Factor): #傳入為別的Factor對象，復制對象 self.factor_list = [i for i in arg.factor_list] elif isinstance(arg, int): #傳入是數字 self._factor(arg) def _factor(self, n): self.factor_list = [] x = 2 while (x * x <= n): if n % x == 0: k = 0 while n % x == 0: n //= x k += 1 self.factor_list.append((x, k)) x += 1 if n != 1: self.factor_list.append((n, 1))
上面Factor()不帶參數時，實際上等同于Factor(1)。
再加入一些運算，包括轉整數、乘法、乘方、除法、n次根等，而加、減法我們并不關心，畢竟對我們問題的解決沒有任何幫助。另外，我們希望這些因式分解對象使用平常的Python運算符，比如乘法的*,乘方的**,除法的/，這樣可以做到運算符的多態(polymorphic)，從而達到泛型(generic)。這一點在別的語言里也可以做到，比如C++我們可以為各個類型重載運算符、函數，再比如Haskell的typeclass也可以讓各個類型使用相同的函數名、運算符。我們在這里使用Python，語言級別提供了自定義class對運算符的支持，那就是魔術方法(magic method)，也就是那些兩個下劃線開頭兩個下劃線結尾的方法，比如__add__(用來重載加法)，__mul__(用來重載乘法)。我們把乘方和n次方根都用乘方符號(**)來表示，但浮點數一般并不能精確的反應分數，我們就采用Python自帶的分數類(from fractions import Fraction)。
考慮一下開方運算，對于解題有幫助的開方運算定義如下:a開n次方意思是$max\{x|x \in Z^+ \land x^n|a\}$
比如$72$開$2$次方結果為$6$
在這樣的定義下，我們重載__int__, __mul__, __truediv__, __power__以實現Factor對象的加法、乘法、除法、乘方
其中除法我們只考慮整除的情況，這些并不難實現，讀者可以自行實現。
再者，我們自然得定義一下序列以便把所有的分解排成一個全序集。
比如，我們考慮$5400$的所有分解，如下：
$(5400)$
$(2 \quad 2700)$
$(3 \quad 1800)$
$(6 \quad 900)$
$(5 \quad 1080)$
$(10 \quad 540)$
$(15 \quad 360)$
$(30 \quad 180)$
$(2 \quad 2 \quad 1350)$
$(2 \quad 6 \quad 450)$
$(2 \quad 10 \quad 270)$
$(2 \quad 30 \quad 90)$
$(3 \quad 3 \quad 600)$
$(3 \quad 6 \quad 300)$
$(3 \quad 15 \quad 120)$
$(3 \quad 30 \quad 60)$
$(6 \quad 6 \quad 150)$
$(6 \quad 30 \quad 30)$
考慮$5400$因式分解為$2^3\times 3^3 \times 5^2$
它有三個質因數$2,3,5$
將上面的每一行里的每個數都寫為$2,3,5$的冪乘積(沒有則填0次冪)，并且順序為$5,3,2$這樣從大到小，那么則為
$({5}^{2} \times {3}^{3} \times {2}^{3})$
$({5}^{0} \times {3}^{0} \times {2}^{1} \quad {5}^{2} \times {3}^{3} \times {2}^{2})$
$({5}^{0} \times {3}^{1} \times {2}^{0} \quad {5}^{2} \times {3}^{2} \times {2}^{3})$
$({5}^{0} \times {3}^{1} \times {2}^{1} \quad {5}^{2} \times {3}^{2} \times {2}^{2})$
$({5}^{1} \times {3}^{0} \times {2}^{0} \quad {5}^{1} \times {3}^{3} \times {2}^{3})$
$({5}^{1} \times {3}^{0} \times {2}^{1} \quad {5}^{1} \times {3}^{3} \times {2}^{2})$
$({5}^{1} \times {3}^{1} \times {2}^{0} \quad {5}^{1} \times {3}^{2} \times {2}^{3})$
$({5}^{1} \times {3}^{1} \times {2}^{1} \quad {5}^{1} \times {3}^{2} \times {2}^{2})$
$({5}^{0} \times {3}^{0} \times {2}^{1} \quad {5}^{0} \times {3}^{0} \times {2}^{1} \quad {5}^{2} \times {3}^{3} \times {2}^{1})$
$({5}^{0} \times {3}^{0} \times {2}^{1} \quad {5}^{0} \times {3}^{1} \times {2}^{1} \quad {5}^{2} \times {3}^{2} \times {2}^{1})$
$({5}^{0} \times {3}^{0} \times {2}^{1} \quad {5}^{1} \times {3}^{0} \times {2}^{1} \quad {5}^{1} \times {3}^{3} \times {2}^{1})$
$({5}^{0} \times {3}^{0} \times {2}^{1} \quad {5}^{1} \times {3}^{1} \times {2}^{1} \quad {5}^{1} \times {3}^{2} \times {2}^{1})$
$({5}^{0} \times {3}^{1} \times {2}^{0} \quad {5}^{0} \times {3}^{1} \times {2}^{0} \quad {5}^{2} \times {3}^{1} \times {2}^{3})$
$({5}^{0} \times {3}^{1} \times {2}^{0} \quad {5}^{0} \times {3}^{1} \times {2}^{1} \quad {5}^{2} \times {3}^{1} \times {2}^{2})$
$({5}^{0} \times {3}^{1} \times {2}^{0} \quad {5}^{1} \times {3}^{1} \times {2}^{0} \quad {5}^{1} \times {3}^{1} \times {2}^{3})$
$({5}^{0} \times {3}^{1} \times {2}^{0} \quad {5}^{1} \times {3}^{1} \times {2}^{1} \quad {5}^{1} \times {3}^{1} \times {2}^{2})$
$({5}^{0} \times {3}^{1} \times {2}^{1} \quad {5}^{0} \times {3}^{1} \times {2}^{1} \quad {5}^{2} \times {3}^{1} \times {2}^{1})$
$({5}^{0} \times {3}^{1} \times {2}^{1} \quad {5}^{1} \times {3}^{1} \times {2}^{1} \quad {5}^{1} \times {3}^{1} \times {2}^{1})$
取指數，則為以下的列
$2, 3, 3$
$0, 0, 1, 2, 3, 2$
$0, 1, 0, 2, 2, 3$
$0, 1, 1, 2, 2, 2$
$1, 0, 0, 1, 3, 3$
$1, 0, 1, 1, 3, 2$
$1, 1, 0, 1, 2, 3$
$1, 1, 1, 1, 2, 2$
$0, 0, 1, 0, 0, 1, 2, 3, 1$
$0, 0, 1, 0, 1, 1, 2, 2, 1$
$...$
這個順序關系一目了然，是以指數序列大小的順序排列的。
我們考慮用這個順序來取出一個正整數所有的正約數，讓Factor加入一個next函數，來取下一個約數。
于是以下代碼遍歷參數n的所有正約數:
def traverse_all_divisors(n): a = Factor(n) b = Factor() print(int(b)) #循環獲得排序下的下一個約數直到不再有約數 while a.next(b): print(int(b))
比如，traverse_all_divisors(72)會依次打印72所有的正約數
1
2
4
8
3
6
12
24
9
18
36
72
以上來看并非數值從小到大，但是如果分解成指數的形式
1 [0, 0]
2 [0, 1]
4 [0, 2]
8 [0, 3]
3 [1, 0]
6 [1, 1]
12 [1, 2]
24 [1, 3]
9 [2, 0]
18 [2, 1]
36 [2, 2]
72 [2, 3]
上面則很容易看出其升序
Factor的next方法實現并不難，從低位往高位依次遍歷，和數數一樣的做法。
def next(self, s): len_self = len(self.factor_list) len_s = len(s.factor_list) #用index_self和index_s作為下標來遍歷 index_self = 0 index_s = 0 #依次來比較self和s while True: if index_self >= len_self: return False xa, ya = self.factor_list[index_self] index_self += 1 if index_s >= len_s: s.factor_list = [(xa, 1)] return True xb, yb = s.factor_list[index_s] index_s += 1 if xa != xb or ya != yb: break if xa != xb: s.factor_list = [(xa, 1), (xb, yb)] + s.factor_list[index_s:] return True #ya != yb s.factor_list = [(xa, yb + 1)] + s.factor_list[index_s:] return True
Python沒有do/while結構，上面的while True與最后if-break是模擬do/while的寫法。
有了以上完整的Factor實現之后，我們就可以按照上述所說的順序來依次生成所有的分解，串成一個迭代器。
Python對迭代器的實現其實很簡單：迭代器是一個class，實現__iter__方法返回self，__next__方法每次調用返回下一個值，當沒有下一個值則發出StopIteration異常。
按照上述所說，以下給出了gen_abel的構造函數，__iter__和__next__：
class gen_abel(object): def __init__(self, n): self.whole_factor = Factor(n) self.next_value = [self.whole_factor] def __iter__(self): return self def __next__(self): if self.next_value: ret = list(map(int, self.next_value)) self._next() return ret raise StopIteration
可以看到，保留兩個屬性，一個是whole_factor來表示n的因式分解，另一個next_value是下一次next所得到的結果，為了區分是否下一次next還有結果，則此處我們先約定沒有下一次next結果則next_value為None。按照之前所說的順序，長度為1的分解是排在最開始的，所以構造函數里給next_value的初值為 [self.whole_factor]。
接下去最后的任務就是實現這個_next函數了，它就是找whole_factor的下一個分解
def _next(self): length = len(self.next_value) #依次調整self.next_value[i:]的分解 for i in range(length - 2, -1, -1): if self._try_next(length, i): return #只能分解長度加1 length += 1 for a, k in self.whole_factor.factor_list: #只需要找到第一個質數的冪不小于length的即可完成分解 if k >= length: t = Factor([(a, 1)]) t2 = self.whole_factor / Factor([(a, length - 1)]) self.next_value = [t] * (length - 1) + [t2] return #實在沒有了，則遍歷完了所有分解，設置為None self.next_value = None
_try_next的實現
def _try_next(self, length, index): #把最后幾項乘起來,嘗試重新分配 t = Factor() for i in self.next_value[index:]: t *= i #r1是總共還可以分配的 r1 = Factor(t) if index != 0: r1 /= Factor(self.next_value[index - 1]) ** (length - index) #這個時候就是開方運算了 r1 = r1 ** Fraction(1, length - index) r2 = Factor(self.next_value[index]) if index != 0: r2 /= self.next_value[index - 1] #r2找個緊接著排序的值 if r1.next(r2): ret = self.next_value[0:index] if index != 0: r2 *= self.next_value[index - 1] for j in range(length - index - 1): ret.append(r2) ret.append(t / r2 ** (length - index - 1)) self.next_value = ret return True return False
Scheme實現
我鐘愛的Lisp，怎么可以少得了它呢，以下鏈接是我寫的實現代碼。
它用了Lisp的一種惰性計算模型——流(stream)，其實和Python的生成器/迭代器沒啥本質上的區別。
三個實現包含著之前的兩種Python實現，以及未寫的基于因式分解提速的遞歸生成器同樣算法。
浙公網安備 33010602011771號