在Python中，从生成元构建循环子群

Question

在12的模运算中进行加法，也就是我们说的整数模12，范围是从0到11：

1 generates [0,1,2,3,4,5,6,7,8,9,10,11] 

（从0开始，不断加1；当我们加到11再加1，就会回到0）

同样的道理：

2 generates [0,2,4,6,8,10]
3 generates [0 3 6 9]
9 generates [0,9,6,3] <-- notice order is important

我该如何根据一个特定的生成元来创建这个子群呢？

Answer 1

你可以像这样创建一个生成器，来实现你想要的功能：

from itertools import imap, count

def subgroup(step, start=0, modulo=12):
    yield start
    for z in imap(lambda x: x%modulo, count(start+step, step)):
      if z == start:
          return
      else:
          yield z

输出结果：

>>> list(subgroup(9))
[0, 9, 6, 3]
>>> list(subgroup(3))
[0, 3, 6, 9]
>>> list(subgroup(2))
[0, 2, 4, 6, 8, 10]

这个生成器会不断生成序列中的下一个项目，直到出现重复的start为止。

Answer 2

我猜你指的是加法子群 Z * g，其中 Z 是整数的集合。如果你想要准确的顺序，可以直接计算一下：

def subgroup(n, g):
    x = 0
    while True:
        yield x
        x = (x + g) % n
        if x == 0: 
            break

当然，如果顺序不重要的话，由 g 产生的子群是

{ G * k for k in xrange((n - 1) // G + 1) }

对于 G = gcd(g, n)。