> < ^ From:

> < ^ Subject:

Mr. Aslam wrote:

------------------------- Dear Gap Forum,

I am looking for an algorithm(s) that would enumerate

a permutation group (from a set of genrators) such

that each element of the

group is represented as a product of the disjoint permutations

(which would be from the set of the generators).

That is if each element pi of the group G is represented as

pi = g1*g2* ... gr ,

(where r is clearly a polynomial in the degree of the group),

then g1,g2, .. gr are mutually disjoint.

Here the size of set of generators could be a polynomial in r.

Clearly, it is not important whether the generators are strong are not.

Hope to receive some references in this direction.

Thanking you all. ------------------------------

It follows a gap program enumerating the first n shortest

words in the generators written by Sebastian Egner and me:

#F EnumeratePermGroup( <permgroup> [, <nrElements>] )

#F enumerates the group up to nrElements. If nrElements

#F is omitted then [1000..10000] elements are produced

#F such that the largest length is completed.

#F The group-words in G.generators and G.abstractGenerators

#F are generated in order (with respect to the order on *words*

#F as defined by GAP) and stored. The function returns nothing.

#F Note that G.abstractGenerators may well contain words.

#F The result of the enumeration is stored as

#F

#F G.shortPairs

#F a set of pairs [word, perm] which contains the

#F specified number of shortest elements of the group.

#F In particular word is the unique minimal word in the

#F given abstract generators which represents perm.

#F

EnumeratePermGroup := function ( arg ) local G, # the group to enumerate nrElements, # number of elements to generate wordGens, # flag if G.abstractGenerators contains words border, # priority queue for the border to expand first, # index of first element of border maxFirst, # max. number of leading holes in border table, # list with holes indexed by hash value of lists of pairs maxTable, # [1..maxTable] is range of hash values size, # number of elements in table minSize, # minimum number of elements if nrElements = "automatic" maxSize, # maximum number of elements if nrElements = "automatic" lengths, # lengths[k] is number of elements of length k nextLength, # prediction of lengths[Length(lengths)+1] printedLength, # maximal k such that lengths[k] has been printed x, g, # [word, perm], [abstr. gen., gen.] xg, xg2, # product x*g; 2nd component h; # hash value for x*g

# parameter defaults minSize := 1000; maxSize := 10000; maxTable := 10007; # or 997 (primes around 10^4 or 10^3) maxFirst := 100; if Length(arg) = 1 and IsPermGroup(arg[1]) then G := arg[1]; nrElements := "automatic"; elif Length(arg) = 2 and IsPermGroup(arg[1]) and IsInt(arg[2]) then G := arg[1]; nrElements := arg[2]; if nrElements < 1 then Error("nrElements must be positive"); fi; else Error("usage: EnumeratePermGroup( <permgroup> [, <nrElements>] )"); fi; MakeGeneratorPairs(G);# recognize if words of words are to be generated

wordGens := ForAny(G.generatorPairs, x -> LengthWord(x[1]) > 1);

if wordGens and nrElements = "automatic" then

nrElements := minSize;

fi;InfoASC1(

"#I EnumeratePermGroup uses hash table of size ", maxTable, "\n"

);

if not wordGens then

InfoASC1("#I exactly 1 permutation of length 0\n");

fi;# initialize hash table table := [ ]; if nrElements <> "automatic" then maxTable := nrElements; while maxTable > 1 and not IsPrimeInt(maxTable) do maxTable := maxTable - 1; od; fi; table[ HashPerm(maxTable, ()) ] := [ [IdWord, ()] ]; size := 1; lengths := [ ]; nextLength := 1; printedLength := 0; # initialize border border := [ [IdWord, ()] ]; first := 1;# orderly generation of [word, perm]-pairs

while IsBound(border[first]) and size < nrElements do

# get x as first in border

x := border[first];

Unbind(border[first]);

first := first + 1;

if first > maxFirst or not IsBound(border[first]) then

SqueezeList(border);

first := 1;

fi;

# expand x in every direction g

for g in G.generatorPairs do# check if x*g has been generated before xg2 := x[2] * g[2]; h := HashPerm(maxTable, xg2); if not IsBound(table[h]) or ForAll(table[h], y -> y[2] <> xg2) then# add x*g to the table xg := [ x[1] * g[1], xg2 ]; if not IsBound(table[h]) then table[h] := [ ]; fi; Add(table[h], xg); Add(border, xg); size := size + 1; if LengthWord(xg[1]) > Length(lengths) then

>>># step to next length for the elements

>>>while LengthWord(xg[1]) > Length(lengths)+1 do

>>> Add(lengths, 0);

>>>od;

>>>Add(lengths, 1);# predict final value of lengths[Length(lengths)] if Length(lengths) = 1 then nextLength := Length(G.generatorPairs); elif Length(lengths) = 2 then nextLength := nextLength * (nextLength - 1); elif lengths[Length(lengths)-2] > 0 then nextLength := QuoInt( lengths[Length(lengths)-1]^2, lengths[Length(lengths)-2] ); fi;# print information on the lengths if Length(lengths) > 1 and not wordGens then while printedLength < Length(lengths)-2 do printedLength := printedLength + 1; InfoASC1( "#I exactly ", lengths[printedLength], " permutations of length ", printedLength, "\n" ); od; printedLength := printedLength + 1; InfoASC1( "#I exactly ", lengths[printedLength], " permutations of length ", printedLength, " (predicting ", nextLength, " for next length)\n" ); fi;>>else

# simply count xg in lengths if LengthWord(xg[1]) > 0 then lengths[LengthWord(xg[1])] := lengths[LengthWord(xg[1])] + 1; fi; fi;>># check if enough elements have been generated

>>if

>> nrElements = "automatic" and lengths[Length(lengths)] = 1 and

>> size > minSize and size + nextLength > maxSize or

>> IsInt(nrElements) and

>> size >= nrElements

>>then# make the set of pairs

G.shortPairs := Concatenation(table);

Sort(G.shortPairs);

if nrElements = "automatic" and Number(border) > 0 then

# remove the single element of largest length

Unbind(G.shortPairs[Length(G.shortPairs)]);

fi;

IsSet(G.shortPairs);return; fi; fi; od; od;

# make the set of pairs

G.shortPairs := Concatenation(table);

Sort(G.shortPairs);

if

nrElements = "automatic" and

Number(border) > 0 and

lengths[Length(lengths)] = 1 and

LengthWord(G.shortPairs[Length(G.shortPairs)][1]) =

Length(lengths)

then

Unbind(G.shortPairs[Length(G.shortPairs)]);

fi;

IsSet(G.shortPairs);

end;

> < [top]