#############################################################################
##
#W  trans.grp         GAP transitive groups library          Alexander Hulpke
##
#H  @(#)$Id: trans.grp,v 4.23 2003/11/16 03:09:32 gap Exp $
##
#Y  Copyright (C)  1997,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
##
##  This file contains the routines for the transitive groups library
##
Revision.trans_grp:=
  "@(#)$Id: trans.grp,v 4.23 2003/11/16 03:09:32 gap Exp $";

#############################################################################
##
## tell GAP about the component
##
DeclareComponent("trans","1.0");

Unbind(TRANSGRP);
Unbind(TRANSPROPERTIES);

#############################################################################
##
#V  TRANSGRP  . . . . . . . . . generators and names of the transitive groups
##  List contains one list per degree. Entries are lists itself
##  for each group,starting with generators,then the name.

TRANSGRP := [[[(),"1 = C(1)"]],

[[(1,2),"C(2) = S(2) = 2"]],

[[(1,2,3),"C(3) = A(3) = 3"],[(1,3),(1,2),"S(3)"]],

[[(1,2,3,4),"C(4) = 4"],
[(1,4)(2,3),(1,2)(3,4),"E(4) = 2[x]2"],
[(1,2,3,4),(1,3),"D(4)"],
[(1,3,4),(2,3,4),"A(4)"],
[(1,4),(1,2),(2,3),"S(4)"]],

[[(1,2,3,4,5),"C(5) = 5"],
[(1,2,3,4,5),(1,4)(2,3),"D(5) = 5:2"],
[(1,2,3,4,5),(1,2,4,3),"F(5) = 5:4"],
[(1,4,5),(2,4,5),(3,4,5),"A(5)"],
[(1,5),(1,2),(2,3),(3,4),"S(5)"]],

[[(1,2,3,4,5,6),"C(6) = 6 = 3[x]2"],
[(1,3,5)(2,4,6),(1,4)(2,3)(5,6),"D_6(6) = [3]2"],
[(1,2,3,4,5,6),(1,4)(2,3)(5,6),"D(6) = S(3)[x]2"],
[(1,4)(2,5),(1,3,5)(2,4,6),"A_4(6) = [2^2]3"],
[(2,4,6),(1,4)(2,5)(3,6),"F_18(6) = [3^2]2 = 3 wr 2"],
[(3,6),(1,3,5)(2,4,6),"2A_4(6) = [2^3]3 = 2 wr 3"],
[(1,4)(2,5),(1,3,5)(2,4,6),(1,5)(2,4),"S_4(6d) = [2^2]S(3)"],
[(1,4)(2,5),(1,3,5)(2,4,6),(1,5)(2,4)(3,6),
"S_4(6c) = 1/2[2^3]S(3)"],
[(2,4,6),(1,5)(2,4),(1,4)(2,5)(3,6),"F_18(6):2 = [1/2.S(3)^2]2"],
[(2,4,6),(1,5)(2,4),(1,4,5,2)(3,6),"F_36(6) = 1/2[S(3)^2]2"],
[(3,6),(1,3,5)(2,4,6),(1,5)(2,4),
"2S_4(6) = [2^3]S(3) = 2 wr S(3)"],
[(1,2,3,4,6),(1,4)(5,6),"L(6) = PSL(2,5) = A_5(6)"],
[(2,4,6),(2,4),(1,4)(2,5)(3,6),
"F_36(6):2 = [S(3)^2]2 = S(3) wr 2"],
[(1,2,3,4,6),(1,2)(3,4)(5,6),"L(6):2 = PGL(2,5) = S_5(6)"],
[(1,5,6),(2,5,6),(3,5,6),(4,5,6),"A(6)"],
[(1,6),(1,2),(2,3),(3,4),(4,5),"S(6)"]],

[[(1,2,3,4,5,6,7),"C(7) = 7"],
[(1,2,3,4,5,6,7),(1,6)(2,5)(3,4),"D(7) = 7:2"],
[(1,2,3,4,5,6,7),(1,2,4)(3,6,5),"F_21(7) = 7:3"],
[(1,2,3,4,5,6,7),(1,3,2,6,4,5),"F_42(7) = 7:6"],
[(1,2,3,4,5,6,7),(1,2)(3,6),"L(7) = L(3,2)"],
[(1,6,7),(2,6,7),(3,6,7),(4,6,7),(5,6,7),"A(7)"],
[(1,7),(1,2),(2,3),(3,4),(4,5),(5,6),"S(7)"]]];


#############################################################################
##
#V  TRANSPROPERTIES . . . . . . . . . property list for the transitive groups
##
##  This list is in the same order as the groups generators. For each group,
##  properties are stored as follows: 
##
##      <size>:         Size of the group
##      <primitive>:    1 indicates, that the group operates primitive
##      <transitivity>: Transitivity
##      <sign>:         Sign
##      <shapes>:       List of all occurring shapes (except ()), sorted
##                      according to the ordering of the Partitions command
##      <2Set>:         Orbits on 2-Sets
##      <2Seq>:         Orbits on 2-Sequences
##      <3Set>:         Orbits on 3-Sets
##      <special>:      following entries mark special properties, which
##       ...            are coded as [type,description1,description2,...] .
##                      The list starts with orbit lengths:
##                      
##      Types:
##      1               1-Set=Pts.
##      2               2-Set
##      3               3-Set
##      4               4-Set
##      5               5-Sets
##      6               i/2-Diff (only possible with even number of points)
##      8               Blocks
##      9               2Seq
##
##           20+b       alternating Subgroup on b
##
##        100*a+b       factor group by operation on the b cosets of a
##                      type a stabilizer; description field gives the
##                      number of this factor group as TransitiveGroup
##       1000*a+10*b+c  factor group by operation on the b cosets of
##                      a type a stabilizer operates on c:
##                      description fields are a list for each of the
##                      possible stabilizers
##      10000*a+10*b+c  type a stabilizer of index b operation on c:
##                      description fields are a list for each of the
##                      possible stabilizers, split again for the
##                      (raw-split) due to the Orbits of <G> itself.
##
##      All Orbit information is coded as a list in which each entry has
##      the form 
##      SignOperation*( 1000*(number of orbits with this description-1)
##                              +length)
##
##      Group theoretic information that cannot be used by the Galois
##      determination routines is indicated by a negative sign:
##
##      -50             Size of the derived subgroup
##      -60             Size of the Frattini subgroup
##      -70             Number of normal subgroups
##
##      some special cases are not discriminated completely by this
##      list. The program will deal with them separately.

TRANSPROPERTIES := [

[[1,1,1,1,[],0,0,0]],

[[2,1,2,-1,[true],[1],[-2],0]],

[[3,1,1,1,[false,true],[3],[1003],0],
[6,1,3,-1,[true,true],[-3],[-6],0]],

[[4,0,1,-1,[false,true,false,true],[-4,-2],[-2004],0],
[4,0,1,1,[false,true,false,false],[-2002],[2004],0],
[8,0,1,-1,[true,true,false,true],[-4,-2],[-4,8],0],
[12,1,2,1,[false,true,true,false],[6],[12],0],
[24,1,4,-1,[true,true,true,true],[6],[-12],0]],

[[5,1,1,1,[false,false,false,false,false,true],[1005],[3005],[1005]],
[10,1,1,1,[false,true,false,false,false,true],[1005],[-1010],[1005]],
[20,1,2,-1,[false,true,false,false,true,true],[-10],[-20],[-10],[29,[-1010]]],
[60,1,3,1,[false,true,true,false,false,true],[10],[20],[10]],
[120,1,5,-1,[true,true,true,true,true,true],[-10],[-20],[-10],[29,[20]]]],

[[6,0,1,-1,[false,false,true,false,false,true,false,false,false,true],
[-1006,3],[-4006],[-2006,-2]],
[6,0,1,-1,[false,false,true,false,false,true,false,false,false,false],
[-2003,-6],[-4006],[-2006,-2]],
[12,0,1,-1,[false,true,true,false,false,true,false,false,false,true],
[-1006,-3],[-6,1012],[-6,-2,12]],
[12,0,1,1,[false,true,false,false,false,true,false,false,false,false],
[3,12],[6,1012],[1004,1006]],
[18,0,1,-1,[false,false,true,true,false,true,false,false,false,true],
[-9,-6],[-1006,-18],[-18,-2]],
[24,0,1,-1,[true,true,true,false,false,true,false,false,false,true],
[3,12],[-6,1012],[-1006,8]],
[24,0,1,1,[false,true,false,false,false,true,false,true,false,false],
[-12,-3],[6,24],[-1004,12]],
[24,0,1,-1,[false,true,true,false,false,true,true,false,false,false],
[-12,-3],[-6,24],[8,12],[29,[6],[1012]]],
[36,0,1,-1,[false,true,true,true,false,true,false,false,false,true],
[-9,-6],[-18,12],[-18,-2]],
[36,0,1,1,[false,true,false,true,false,true,false,true,false,false],
[6,9],[-18,-12],[-18,-2]],
[48,0,1,-1,[true,true,true,false,false,true,true,true,false,true],
[-12,-3],[-6,24],[8,12],[29,[6],[24]]],
[60,1,2,1,[false,true,false,false,false,true,false,false,true,false],
[15],[30],[1010]],
[72,0,1,-1,[true,true,true,true,true,true,false,true,false,true],
[-9,-6],[-18,-12],[-18,-2]],
[120,1,3,-1,[false,true,true,false,false,true,true,false,true,true],
[15],[-30],[20],[23,[1010]]],
[360,1,4,1,[false,true,false,true,false,true,false,true,true,false],
[15],[30],[20]],
[720,1,6,-1,[true,true,true,true,true,true,true,true,true,true],
[15],[-30],[20],[23,[20]]]],

[[7,1,1,1,[false,false,false,false,false,false,false,false,false,false,
false,false,false,true],[2007],[5007],[4007]],
[14,1,1,-1,[false,false,true,false,false,false,false,false,false,false,
false,false,false,true],[-2007],[-2014],[-2007,-14]],
[21,1,1,1,[false,false,false,false,false,false,true,false,false,false,
false,false,false,true],[21],[1021],[21,1007]],
[42,1,2,-1,[false,false,true,false,false,false,true,false,false,false,
false,false,true,true],[-21],[-42],[-21,-14]],
[168,1,2,1,[false,true,false,false,false,false,true,false,true,false,
false,false,false,true],[21],[42],[7,28]],

[2520,1,5,1,[false,true,false,true,false,true,true,false,true,false,
true,false,false,true],[21],[42],[35]],
[5040,1,7,-1,[true,true,true,true,true,true,true,true,true,true,true,
true,
true,true],[-21],[-42],[35]]]];

#  The following command converts the shape lists into Blists (binary
#  lists), which allows for about 2/3 of memory saved

List([1..7],i->ForAll(TRANSPROPERTIES[i],j->IsBlist(j[5])));

# number of groups within each degree (stored up to 15)
TRANSLENGTHS := [ 1, 1, 2, 5, 5, 16, 7, 50, 34, 45, 8, 301, 9, 63, 104 ];

TRANSNONDISCRIM := [[],[],[],[],[],[],[],[],[],[],[],[[273,292]],[],
[[42,51]],[[37,58],[38,59],[57,67],[65,74],[66,74]]];

TRANSSELECT :=[];
TRANSSIZES  :=[];
TRANSPARTNUM:=[];
InstallFlushableValue(TRANSSHAPEFREQS,[]);

if not IsBound(TRANSDEGREES) or TRANSDEGREES=0 then
  TRANSDEGREES :=7;
  HideGlobalVariables("dir","fnam");
  dir:= DirectoriesLibrary( "trans" );
  fnam:=Filename( dir, Concatenation("trans",String(TRANSDEGREES+1),".grp"));
  while fnam<>fail and IsReadableFile(fnam) do
    TRANSDEGREES:=TRANSDEGREES+1;
    fnam:=Filename( dir, Concatenation("trans",String(TRANSDEGREES+1),".grp"));
  od;
  UnhideGlobalVariables("dir","fnam");
fi;

BIND_GLOBAL("TransGrpLoad",function(deg,nr)
local Tbak,Fbak,flg,sel,i,fname;
  if IsBound(TRANSGRP[deg]) and (nr=0 or IsBound(TRANSGRP[deg][nr])) then
    return;
  fi;
  if deg>TRANSDEGREES then
    Error("transitive groups are known only of degree up to ",
	  TRANSDEGREES);
  else
    HideGlobalVariables("T","F");
    BIND_GLOBAL("T",true);
    BIND_GLOBAL("F",false);
    fname:=Concatenation("trans",String(deg));
    if deg>15 and not IsPrime(deg) then
      if not IsBound(TRANSGRP[deg]) then
	ReadGapRoot( Concatenation( "trans/", fname, ".grp" ) );
        if nr=0 then 
	  UnhideGlobalVariables("T","F");
	  return;
	fi;
      else
	# the groups to be thrown away
	sel:=Difference(Filtered([1..Length(TRANSGRP[deg])],
	                  i->IsBound(TRANSGRP[deg])),TRANSSELECT[deg]);
	if Length(TRANSSELECT[deg])>300 then
	  flg:=TRANSSELECT[deg]{[1..Length(TRANSSELECT[deg])-150]};
	  sel:=Union(flg,sel);
	  TRANSSELECT[deg]:=Difference(TRANSSELECT[deg],flg);
	fi;
        for i in sel do
	  Unbind(TRANSGRP[deg][i]);
	  Unbind(TRANSPROPERTIES[deg][i]);
	od;
      fi;
      Append(fname,WordAlp("abcdefghijklmnopqrstuvwxyz",Int((nr-1)/300)+1));
    fi;

    IsString(fname);

    ReadGapRoot( Concatenation( "trans/", fname, ".grp" ));

    UnhideGlobalVariables("T","F");

    if deg>15 and not IsPrime(deg) then
      sel:=Difference(Filtered([1..Length(TRANSGRP[deg])],
			 i->IsBound(TRANSGRP[deg][i])),TRANSSELECT[deg]);
    else
      TRANSLENGTHS[deg]:=Length(TRANSGRP[deg]);
      TRANSSIZES[deg]:=List(TRANSPROPERTIES[deg],i->i[1]);
      sel:=[1..TRANSLENGTHS[deg]];
    fi;
    # make blists those which are
    ForAll(TRANSPROPERTIES[deg]{sel},i->IsBound(i[5]) and IsBlist(i[5]));
  fi;
  for i in sel do
    MakeImmutable(TRANSGRP[deg][i]);
    MakeImmutable(TRANSPROPERTIES[deg][i]);
  od;
  TRANSPARTNUM[deg]:=NrPartitions(deg);
  TRANSSHAPEFREQS[deg]:=[];
end);

BIND_GLOBAL("TRANSGrp",function(deg,nr)
  if not IsBound(TRANSGRP[deg]) or not IsBound(TRANSGRP[deg][nr]) then
    TransGrpLoad(deg,nr);
  fi;
  if deg>15 and not IsPrime(deg) then
    AddSet(TRANSSELECT[deg],nr);
  fi;
  if nr>TRANSLENGTHS[deg] then
    return "fail";
  fi;
  return TRANSGRP[deg][nr];
end);

BIND_GLOBAL("TRANSProperties",function(deg,nr)
local l;
  if not IsBound(TRANSPROPERTIES[deg]) or
    not IsBound(TRANSPROPERTIES[deg][nr]) then
    TransGrpLoad(deg,nr);
  fi;
  if deg>15 and not IsPrime(deg) then
    AddSet(TRANSSELECT[deg],nr);
  fi;
  if nr>TRANSLENGTHS[deg] then
    return "fail";
  fi;
  l:=TRANSPROPERTIES[deg][nr];
  if IsBound(l[5]) and IsString(l[5]) then
    # translate string to blist
    l:=ShallowCopy(l);
    l[5]:=BlistStringDecode(l[5],TRANSPARTNUM[deg]-1);
    MakeImmutable(l);
    TRANSPROPERTIES[deg][nr]:=l;
  fi;
  return l;
end);

InstallGlobalFunction(NrTransitiveGroups, function(deg)
  if not(deg in [1..TRANSDEGREES]) then
    return fail;
  fi;
  if not IsBound(TRANSLENGTHS[deg]) then
    TransGrpLoad(deg,0);
  fi;
  return TRANSLENGTHS[deg];
end);

InstallGlobalFunction( TransitiveGroup, function(deg,num)
  local gens,i,l,g,s;
  if not(deg in [1..TRANSDEGREES]) then
    Error("degree must be in [1..",TRANSDEGREES,"]");
  fi;
  if not IsBound(TRANSLENGTHS[deg]) then
    TransGrpLoad(deg,num);
  fi;
  if not (num in [1..TRANSLENGTHS[deg]]) then
    Error("maximal number of groups of degree ",deg," is ",
           TRANSLENGTHS[deg]);
  fi;
 
  # special case: Symmetric and Alternating Group
  s:=Factorial(deg);
  if TRANSProperties(deg,num)[1]=s then
    if deg=1 then
      g:=GroupByGenerators( [], () );
    else
      g:=SymmetricGroup(deg);
    fi;
    SetName(g,Concatenation("S",String(deg)));
  elif TRANSProperties(deg,num)[1]*2=s then
    g:=AlternatingGroup(deg);
    SetName(g,Concatenation("A",String(deg)));
  else
    l:=TRANSGrp(deg,num);
    s:=Length(l);
    gens:=[];
    for i in l{[1..s-1]} do
      if IsPerm(i) then
        Add(gens,i);
      else
        if Length(i)=2 then
          Add(gens,TRANSGrp(i[1],i[2])[1]);
        else
          Add(gens,TRANSGrp(i[1],i[2])[i[3]]);
        fi;
      fi;
    od;
    g:= GroupByGenerators( gens, () );
    if l[s]<>"" then
      SetName(g,l[s]);
    else
      SetName(g,Concatenation("t",String(deg),"n",String(num)));
    fi;
  fi;
  SetTransitiveIdentification(g,num);
  return g;
end );

InstallFlushableValue(TRANSCOMBCACHE,[[0],[0],[0]]);
BindGlobal("TransCombinat",function(m,n)
local i,l;
  for i in [1..3] do
    if TRANSCOMBCACHE[i][1]=m and TRANSCOMBCACHE[i][2]=n then
      return TRANSCOMBCACHE[i][3];
    fi;
  od;
  TRANSCOMBCACHE[3]:=TRANSCOMBCACHE[2];
  TRANSCOMBCACHE[2]:=TRANSCOMBCACHE[1];
  l:=Combinations(m,n);
  for i in l do MakeImmutable(i);od;
  Sort(l);
  IsSet(l);
  TRANSCOMBCACHE[1]:=[m,n,l];
  return l;
end);

InstallFlushableValue(TRANSARRCACHE,[[0],[0],[0]]);
BindGlobal("TransArrange",function(m,n)
local i,l;
  for i in [1..3] do
    if TRANSARRCACHE[i][1]=m and TRANSARRCACHE[i][2]=n then
      return TRANSARRCACHE[i][3];
    fi;
  od;
  TRANSARRCACHE[3]:=TRANSARRCACHE[2];
  TRANSARRCACHE[2]:=TRANSARRCACHE[1];
  l:=Arrangements(m,n);
  for i in l do MakeImmutable(i);od;
  Sort(l);
  IsSet(l);
  TRANSARRCACHE[1]:=[m,n,l];
  return l;
end);

BindGlobal("CntOp",function(grp,orb,op)
local l,i,j,sgn;
  l:=[];
  for i in orb do
    i:=Set(Immutable(i));
    sgn:=1;
    j:=1;
    while sgn=1 and j<=Length(GeneratorsOfGroup(grp)) do
      if SignPerm(Permutation(GeneratorsOfGroup(grp)[j],i,op))<0 then 
        sgn:=-1;
      fi;
      j:=j+1;
    od;
    Add(l,sgn*Length(i));
  od;
  l:=Collected(l);
  for i in [1..Length(l)] do
    l[i]:=SignInt(l[i][1])*(1000*(l[i][2]-1)+AbsInt(l[i][1])); 
  od;
  Sort(l);
  return l;
end);

BindGlobal("NumBol",function(b)
  if b then return 1;
       else return 0;
  fi;
end);

BindGlobal("SetsOrbits",function(g,n)
local l,i;
  l:=TransCombinat(MovedPoints(g),n);
  for i in l do MakeImmutable(i);od;
  Sort(l);
  return Orbits(g,l,OnSets);
end); 

BindGlobal("SeqsOrbits",function(g,n)
local l,i;
  l:=TransArrange(MovedPoints(g),n);
  for i in l do MakeImmutable(i);od;
  Sort(l);
  return Orbits(g,l,OnTuples);
end); 

# the (undocumented) `cheap' parameter has the following function:
# not set -> proper test
# true -> return `fail' if not unique ID
# 1    -> ID list if no cheap unique ID
# 2    -> as 1, but do not compute classes (expensive if big!)
InstallMethod(TransitiveIdentification,"generic",true,[IsPermGroup],0,
function(ogrp)
local dom,p,s,t,a,cand,i,grp,deg,aiso,piso,co,cheap;
  cheap:=ValueOption("cheap");
  grp:=ogrp;
  dom:=MovedPoints(grp);
  if not IsTransitive(grp,dom) then
    Error("Group must operate transitive");
  fi;
  deg:=Length(dom);
  if not IsBound(TRANSLENGTHS[deg]) then
    TransGrpLoad(deg,0);
  fi;

  s:=Size(grp);
  if deg>15 then
    cand:=Filtered([1..TRANSLENGTHS[deg]],i->TRANSSIZES[deg][i]=s);
  else
    cand:=Filtered([1..TRANSLENGTHS[deg]],i->TRANSProperties(deg,i)[1]=s);
  fi;
  if Length(cand)>1 and deg>4 then
    co:=CntOp(grp,Orbits(grp,TransCombinat(dom,2),OnSets),OnSets);
    cand:=Filtered(cand,i->TRANSProperties(deg,i)[6]=co);
    if Length(cand)>1 then
      co:=CntOp(grp,Orbits(grp,TransArrange(dom,2),OnTuples),OnTuples);
      cand:=Filtered(cand,i->TRANSProperties(deg,i)[7]=co);
    fi;
    if Length(cand)>1 then
      co:=CntOp(grp,Orbits(grp,TransCombinat(dom,3),OnSets),OnSets);
      cand:=Filtered(cand,i->TRANSProperties(deg,i)[8]=co);
    fi;
  fi;

  Pcgs(grp); # try to enforce solvable calculations further on.
#  if Length(cand)>1 and IsSolvableGroup(grp)
#     and not HasConjugacyClasses(grp) then
#    t:=[];
#    aiso:=IsomorphismPcGroup(grp);
#    a:=Image(aiso,grp);
#    for i in ConjugacyClasses(a) do
#      s:=ConjugacyClass(grp,PreImagesRepresentative(aiso,Representative(i)));
#      SetStabilizerOfExternalSet(s,PreImage(aiso,Centralizer(i)));
#      Add(t,s);
#    od;
#    SetConjugacyClasses(grp,t);
#  fi;

  if Length(cand)>1 and cheap<>2 then
    s:=List(CycleStructuresGroup(grp),i->i=1);
    cand:=Filtered(cand,i->TRANSProperties(deg,i)[5]=s);
  fi;
  if Length(cand)>1 then
    p:=List(cand,i->TransitiveGroup(deg,i));

    # DerivedSubgroups + Frattini Subgroups
    s:=Filtered([1..Length(cand)],i->
	Size(DerivedSubgroup(p[i]))=Size(DerivedSubgroup(grp)));
    if Length(Factors(Size(grp)))=1 then
      s:=Filtered(s,i->
	  Size(FrattiniSubgroup(p[i]))=Size(FrattiniSubgroup(grp)));
    fi;
    cand:=cand{s};
    p:=p{s};
  fi;

  if Length(cand)>1 then
    # Blockl"angen
    t:=List(p,i->Collected(List(AllBlocks(i),Length)));
    s:=Collected(List(AllBlocks(grp),Length));
    s:=Filtered([1..Length(cand)],i->s=t[i]);
    cand:=cand{s};
    p:=p{s};
  fi;

  if Length(cand)>1 then
    # 4-sets
    t:=[4,CntOp(grp,SetsOrbits(grp,4),OnSets)]; 
    s:=Filtered([1..Length(cand)],i->t in TRANSProperties(deg,cand[i])
	or ForAll(TRANSProperties(deg,cand[i]){
	      [9..Length(TRANSProperties(deg,cand[i]))]},j->j[1]<>4));
    cand:=cand{s};
    p:=p{s};
  fi;

  if Length(cand)>1 and cheap<>2 then
    # As all computations, which follow involve only the groups, convert
    # them to PcGroups if possible
    if IsSolvableGroup(grp) then
      s:=Filtered([1..Length(cand)],i->IsSolvableGroup(p[i]));
      cand:=cand{s};
#      aiso:=IsomorphismPcGroup(grp);
#      grp:=Image(aiso,grp);
#
#      piso:=List(p{s},IsomorphismPcGroup);
#      p:=List([1..Length(s)],i->Image(piso[i],p[s[i]]));
      p:=p{s}; 
      List(p,Pcgs); # enforce Pcgs use
#    else
#      aiso:=IdentityMapping(grp);
#      piso:=List(p,IdentityMapping);
    fi;

    # Klassen
    t:=Collected(List(ConjugacyClasses(grp),
                      i->[CycleStructurePerm(Representative(i)),Size(i)]));
    s:=Filtered([1..Length(cand)],i->Collected(List(
           ConjugacyClasses(p[i]),
           j->[CycleStructurePerm(Representative(j)),Size(j)]))=t);
    cand:=cand{s};
    p:=p{s};
  fi;  

  # maximal subgroups
  if cheap=fail and IsSolvableGroup(grp) and Length(cand)>1 then
    t:=Collected(List(MaximalSubgroupClassReps(grp),
      i->[Size(i),Collected(List(Orbits(i,MovedPoints(grp)),Length))]));
    s:=Filtered([1..Length(cand)],k->
         Collected(List(MaximalSubgroupClassReps(p[k]),
	   i->[Size(i),Collected(List(Orbits(i,MovedPoints(grp)),Length))]))=t);
    cand:=cand{s};
    p:=p{s};
    if Length(cand)>1 then
      a:=Filtered(t,i->i[2]<=5 and Length(i[1][2])=1 and i[1][2][1][2]=1);
      a:=List(a,i->i[1][1]);
      t:=Collected(List(Filtered(MaximalSubgroupClassReps(grp),
		  i->Size(i) in a and Length(Orbits(i,MovedPoints(grp)))=1),
		  x->TransitiveIdentification(x:cheap)));
      s:=Filtered([1..Length(cand)],
	  k->Collected(List(Filtered(MaximalSubgroupClassReps(p[k]),
		  i->Size(i) in a and Length(Orbits(i,MovedPoints(p[k])))=1),
		  x->TransitiveIdentification(x:cheap)))=t);
      cand:=cand{s};
      p:=p{s};
    fi;
  fi;

  if cheap=fail and Length(cand)>1 and not IsSolvableGroup(grp) then
    # NormalSubgroups (some solvable groups have too many)
    t:=Collected(List(NormalSubgroups(grp),Size));
    s:=Filtered([1..Length(cand)],
                i->Collected(List(NormalSubgroups(p[i]),Size))=t);
    cand:=cand{s};
    p:=p{s};
  fi;  

  if cheap=fail and Length(cand)>1 and Size(grp)<3000 then
    # Subgroups
    Info(InfoWarning,2,"TransId: test Subgroups ",cand);
    t:=Collected(List(ConjugacyClassesSubgroups(Group(GeneratorsOfGroup(grp))),
                      i->[Size(Representative(i)),Size(i)]));
    s:=Filtered([1..Length(cand)],i->Collected(List(
           ConjugacyClassesSubgroups(Group(GeneratorsOfGroup(p[i]))),
           i->[Size(Representative(i)),Size(i)]))=t);
    cand:=cand{s};
    p:=p{s};
  fi;  

  if cheap=fail and Length(cand)>1 then
    # two special cases in degree 30
    if Length(dom)=30 and 2230 in cand or 4335 in cand then
      Info(InfoWarning,2,"TransId: Isomorphism Test",cand);
      cand:=First(cand,i->IsomorphismGroups(grp,
         TransitiveGroup(30,i):nogensyssearch:=true)<>fail);
      return cand;
    fi;
    # now finally the hard test: Test for conjugacy
    Info(InfoWarning,2,"TransId: Conjugacy Test",cand);
    s:=SymmetricGroup(Maximum(dom));
#    if IsSolvableGroup(grp) then
#      grp:=PreImage(aiso,grp);
#      p:=List([1..Length(p)],i->PreImage(piso[i],p[i]));
#    fi; 
    grp:=AsSubgroup(s,grp);
    p:=List(p,i->AsSubgroup(s,i));
    s:=Filtered([1..Length(cand)],i->IsConjugate(s,grp,p[i]));
    cand:=cand{s};
    p:=p{s};
  fi;

  if Length(cand)=1 then
    return cand[1];
  elif cheap=true then
    return cand;
  elif cheap<>fail then
    return cand;
  else
    Error("Uh-Oh, this should never happen ",cand);
  fi;
end);

#############################################################################
##
#F  SelectTransitiveGroups(arglis,alle)  . . . . . selection function
##
BIND_GLOBAL("SelectTransitiveGroups",function(arglis,alle)
local i,j,a,b,l,p,deg,gut,g,grp,nr,f;
  l:=Length(arglis)/2;
  if not IsInt(l) then
    Error("wrong arguments");
  fi;
  deg:=[2..TRANSDEGREES];
  p:=Position(arglis,NrMovedPoints);
  if p<>fail then
    p:=arglis[p+1];
    if IsInt(p) then
      p:=[p];
    fi;
    if IsList(p) then
      f:=not IsSubset(deg,p);
      deg:=Intersection(deg,p);
    else
      f:=true;
      deg:=Filtered(deg,p); 
    fi;
  else
    f:=true; #warnung weil kein Degree angegeben ?
  fi;
  gut:=[];
  for i in deg do
    if not IsBound(TRANSLENGTHS[i]) then
      TransGrpLoad(i,0);
    fi;
    gut[i]:=[1..TRANSLENGTHS[i]];
  od;

  # special treatment for Size for degrees larger than 15
  a:=Position(arglis,Size);
  if a<>fail then
    a:=arglis[a+1];
    for i in Filtered(deg,i->i>15 and not IsPrime(i)) do
      if IsFunction(a) then
        gut[i]:=Filtered(gut[i],j->a(TRANSSIZES[i][j]));
      elif IsList(a) then
        gut[i]:=Filtered(gut[i],j->TRANSSIZES[i][j] in a);
      else
        gut[i]:=Filtered(gut[i],j->TRANSSIZES[i][j]=a);
      fi;
    od;
  fi;

  # find the properties we have not stored
  p:=[];
  for i in [1..l] do
    if not arglis[2*i-1] in
      [NrMovedPoints,Size,Transitivity,SignPermGroup,IsPrimitive] then
      Add(p,arglis{[2*i-1,2*i]}); 
    fi;
  od;

  for i in [1..l] do
    a:=arglis[2*i-1];
    b:=arglis[2*i];

    # get all cheap properties first
    if a=NrMovedPoints then
      f:=false;
      if IsInt(b) then
        b:=[b];
      fi;
      if IsList(b) then
        b:=Set(b);
        if not IsSubset(deg,b) then
          f:=true;
        fi;
        deg:=Intersection(deg,b);
      else
        # b is a function (wondering, whether anyone will ever use it...)
        f:=true;
        deg:=Filtered(deg,b);
      fi;
    elif a=Size or a=Transitivity or a=SignPermGroup then
      if a=Size then
        nr:=1;
      elif a=Transitivity then
        nr:=3;
      else
        nr:=4;
      fi;
      for i in deg do
	gut[i]:=Filtered(gut[i],j->STGSelFunc(TRANSProperties(i,j)[nr],b));
      od;
    elif a=IsPrimitive then
      b:=NumBol(b);
      for i in deg do
        gut[i]:=Filtered(gut[i],j->TRANSProperties(i,j)[2]=b);
      od;
    fi;
  od;

  if f then
    Print("#W  AllTransitiveGroups: Degree restricted to [2..",
          TRANSDEGREES,"]\n");
  fi;

  # the rest is hard:  
  grp:=[];
  for i in deg do
    for nr in gut[i] do
      g:=TransitiveGroup(i,nr);
      if ForAll(p,i->STGSelFunc(i[1](g),i[2])) then
        if alle then
          Add(grp,g);
        else
          return g;
        fi;
      fi;
    od;
  od;

  return grp;
end);

#############################################################################
##
#F  AllTransitiveGroups( <fun>, <res>, ... ) . . . . . . . selection function
##
BIND_GLOBAL("AllTransitiveGroups",function ( arg )
  return SelectTransitiveGroups(arg,true);
end);

#############################################################################
##
#F  OneTransitiveGroup( <fun>, <res>, ... ) . . . . . . . selection function
##
BIND_GLOBAL("OneTransitiveGroup",function ( arg )
local sel;
  sel:=SelectTransitiveGroups(arg,false);
  if sel=[] then
    return fail;
  else
    return sel;
  fi;
end);

#############################################################################
##
#E

