有限Abel群的结构(3)

技术分享 8个月前 (08-01) 0 999+

　　版权申明：本文为博主窗户(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}^{ile n}{a_i})*a_n|N$

也就是

$(a_1,a_2...a_n,frac{N}{prod_{i=1}^{ile n}{a_i}})$

是后面仅剩一项的情况

如果

$exists a_{n+1}:a_n|a_{n+1} land (prod_{i=1}^{ile 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}^{ile 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}^{ile 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^3times 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