> < ^ Date: Tue, 26 Mar 1996 15:18:00 +0100 (MET)
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
< ^ Subject: Re: Dimino's algorithm
Ernesto P. Adorio wrote in his mail message of 1996/03/23

I used the ff. algorithm to generate sequentially n elements of a group
before I discovered GAP.
...code omitted...
Is this just a well-known variant of the Dimino's algorithm?

No this is just a simple implementation of the orbit algorithm.
At least it is if you replace the line

           if a*g not in C or a*g not in A or a*g not in N
                           ^^              ^^
with

           if a*g not in C and a*g not in A and a*g not in N
                           ^^^              ^^^
Otherwise I think you algorithm may not terminate.

Your algorithm can be improved slightly by directly moving new elements
into C, so one membership test (instead of the three above) suffices.

C := [ e ];    # set of all found elements
N := [ e ];    # new elements
while N <> []  do
    A := N;
    N := [];
    for a in A do
        for g in gens do
            if not a*g in C then
                AddSet( C, a*g );
                Add( N, a*g );
            fi;
        od;
    od;
od;

The Dimino algorithm works somewhat different.
First it computes the list of elements of < g_1 >
(the subgroup generated by the first generator).
Then it computes the list of elements of < g_1, g_2 >.
If it finds a new element <g> it adds the whole coset < g_1 > * <g>.
Then it computes the list of elements of < g_1, g_2, g_3 >.
If it finds a new element <g> it adds the whole coset < g_1, g_2 > * <g>.
And so on until it has computed the list of elements of < g_1, ..., g_n >.

C := [ e ];
for i in [1..n]  do
    D := C;
    N := [ e ];
    while reps <> []  do
        A := N;
        N := [];
        for a in A do
            for g in gens{[1..i]} do
                if not a*g in C  then
                    UniteSet( C, D * (a*g) );
                    Add( N, a*g );
                fi;
            od;
        od;
    od;
od;

Since it only tests membership for the representatives of the cosets,
and adds the other elements without membership tests,
it uses fewer membership tests and is therefore faster.
The smaller the indices [ < g_1, ..., g_{i+1} > : < g_1, ..., g_i > ]
are, the more it wins.

Martin.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]