> < ^ From:

< ^ Subject:

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]