> < ^ 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
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) );
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]