有限Abel群的结构(3)

　　版权申明：本文为博主窗户(Colin Cai)原创，欢迎转帖。如要转贴，必须注明原文网址 　　 https://www.cnblogs.com/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