> < ^ Date: Mon, 13 Jul 1998 09:11:55 +0200 (MET DST)
> < ^ From: Markus Pueschel <pueschel@earthlink.net >
> < ^ Subject: Permutation group enumeration by disjoint permutations

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) then
G          := arg;
nrElements := "automatic";
elif Length(arg) = 2 and IsPermGroup(arg) and IsInt(arg) then
G          := arg;
nrElements := arg;
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);
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 * g;
h   := HashPerm(maxTable, xg2);
if
not IsBound(table[h]) or
ForAll(table[h], y -> y <> xg2)
then
```
```# add x*g to the table
xg := [ x * g, xg2 ];
if not IsBound(table[h]) then
table[h] := [ ];
fi;
size := size + 1;
if LengthWord(xg) > Length(lengths) then
```

>>># step to next length for the elements
>>>while LengthWord(xg) > Length(lengths)+1 do
>>>od;

```        # 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) > 0 then
lengths[LengthWord(xg)] := lengths[LengthWord(xg)] + 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)]) =
Length(lengths)
then
Unbind(G.shortPairs[Length(G.shortPairs)]);
fi;
IsSet(G.shortPairs);
end;

> < [top]