> < ^ Date: Sat, 23 Mar 1996 20:22:52 +0800
^ From: Ernesto P. Adorio <adorio@math.upd.edu.ph >
> ^ Subject: Dimino's algorithm

I used the ff. algorithm to generate sequentially n elements of a group
before I discovered GAP. It was slow for interactive use (generating
elements of a plane crystallographic group), but it may interest other
users of GAP. It is written in pseudo-code here.

C = {e} output group initially containing the identity element
A = {e} active block of elements
N = {} set of newly generated elements
G = {g1, g2, ..., gk} set of k generators excluding the identity element
n = number of group elements desired

count = 1
while A <> {}
    for each a in A
       for each g in G
           if a*g not in C or a*g not in A or a*g not in N
                N = N U { a*g}      // U is set union
                count = count + 1
                if count = n
                   return C
                endif
           endif
       next
    next
    C = C U A
    A = N
    N = {}       reset N
wend
return C

Is this just a well-known variant of the Dimino's algorithm?


> < [top]