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;