In Python, construct cyclic subgroup from generator

Question

Using addition in Z modulo 12, (a.k.a the integers mod 12, a.k.a 0 thru 11):

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

(starting at 0 and repeatedly adding 1; 11+1 takes us back to 0)

In the same way:

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

How can I create the subgroup given a particular generator?

Answer 1

I'm assuming you mean the additive subgroup Z * g where Z is the set of integers. If you want the precise order, just compute it:

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

And of course if order is unimportant, the subgroup induced by g is

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

for G = gcd(g, n).

Answer 2

You can create an generator that does what you're asking like this:

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

Output:

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

It will keep generating the next item in the sequence until the start is repeated.