#############################################################################
##
#A  trans.grp                   GAP group library            Alexander Hulpke
#A                                                              & Greg Butler
#A                                                               & John McKay
##
#A  @(#)$Id: trans.grp,v 1.1.1.1 1996/12/11 12:37:17 werner Exp $
##
#Y  Copyright (C)  1996,  Lehrstuhl d f"ur Mathematik,  RWTH Aachen,  Germany
#Y  Copyright (C)  1983,  John McKay, Concordia University,  Montreal, Canada
##
##  This file contains the transitive groups of degree up to 7.
##
#H  $Log: trans.grp,v $
#H  Revision 1.1.1.1  1996/12/11 12:37:17  werner
#H  Preparing 3.4.4 for release
#H
#H  Revision 3.5.1.1  1996/11/13 14:01:15  ahulpke
#H  3.4 modifications
#H
#H  Revision 3.5  1996/11/13 13:59:20  ahulpke
#H  Added new ID routine
#H
#H  Revision 3.4  1996/06/03  15:07:09  ahulpke
#H  changed TRANSGRP and -PROPERTIES to Grp and Properties
#H
#H  Revision 3.3  1995/06/16  14:01:28  ahulpke
#H  changed names to new notation
#H
#H  Revision 3.2  1994/10/22  13:10:23  ahulpke
#H  allow preliminary assignment of TRANSDEGREES
#H
#H  Revision 3.1  1994/06/03  10:35:20  ahulpke
#H  initial revision under RCS
#H
##


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
##      <2Seq>:         Orbits on 2-Sequences
##      <2Set>:         Orbits on 2-Sets
##      <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       derived 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
##                      an 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

Apply([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  := [];

if not IsBound(TRANSDEGREES) then
  TRANSDEGREES := 22;
fi;

#V force global variables T and F to be assigned to avoid syntax errors
if not IsBound(T) then 
  T:="dummyT";
fi;
if not IsBound(F) then 
  F:="dummyF";
fi;

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
    if IsBound(T) then Tbak:=T;fi;
    if IsBound(F) then Fbak:=F;fi;
    T:=true;
    F:=false;
    fname:=Concatenation("trans",String(deg));
    if deg>15 and not IsPrime(deg) then
      if not IsBound(TRANSGRP[deg]) then
	flg:= not ReadPath( GRPNAME, fname, ".grp","ReadTrans");
	if flg then
	    Error( "the transitive group library file '",fname,
		   "' must exist and be readable");
	fi;
        if nr=0 then 
	  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);

    flg:= not ReadPath( GRPNAME, fname, ".grp","ReadTrans");

    if IsBound(Tbak) then T:=Tbak;fi;
    if IsBound(Fbak) then F:=Fbak;fi;

    if flg then
	Error( "the transitive group library file '",fname,
	       "' must exist and be readable");
    fi;

    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]:=Apply(TRANSPROPERTIES[deg],i->i[1]);
      sel:=[1..TRANSLENGTHS[deg]];
    fi;
    ForAll(TRANSPROPERTIES[deg]{sel},i->IsBound(i[5]) and IsBlist(i[5]));
  fi;
end;

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;

TRANSProperties := function(deg,nr)
  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;
  return TRANSPROPERTIES[deg][nr];
end;

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:=Group(());
    else
      g:=SymmetricGroup(deg);
    fi;
    g.name:=Concatenation("S",String(deg));
  elif TRANSProperties(deg,num)[1]*2=s then
    g:=AlternatingGroup(deg);
    g.name:=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:=Group(gens,());
    if l[s]<>"" then
      g.name:=l[s];
    else
      g.name:=ConcatenationString("t",String(deg),"n",String(num));
    fi;
  fi;
  g.transitiveType:=num;
  return g;
end;

SignPermGroup := function(g)
  if ForAll(g.generators,i->SignPerm(i)=1) then
    return 1;
  else
    return -1;
  fi;
end;

AllBlocks := function(g)
local dom,DoBlocks,pool;

  DoBlocks:=function(b)
  local bl,bld,i,t,n;
    bld:=Difference(dom,b);
    bl:=[];
    if not IsPrime(Length(dom)/Length(b)) then
      for i in bld do
	t:=Union(b,[i]);
	n:=Blocks(g,dom,t);
	if Length(n)>1 and #ok durch pool:ForAll(Difference(n[1],t),j->j>i) and
	   not n[1] in pool then
	  t:=n[1];
	  Add(pool,t);
	  bl:=Concatenation(bl,[t],DoBlocks(t));
	fi;
      od;
    fi;
    return bl;
  end;

  if not IsBound(g.allBlocks) then
    dom:=PermGroupOps.MovedPoints(g);
    pool:=[];
    g.allBlocks:=DoBlocks(dom{[1]});
  fi;
  return g.allBlocks;
end;
  

AllCycleStructures := function(n)
local i,j,l,m;
  l:=[];
  for i in Partitions(n) do
    m:=[];
    for j in i do
      if j>1 then
        if IsBound(m[j-1]) then
          m[j-1]:=m[j-1]+1;
        else 
          m[j-1]:=1;
        fi;
      fi;
    od;
    Add(l,m);
  od;
  return l;
end;

CycleStructures := function(g)
local c,l,m,i;
  l:=AllCycleStructures(Length(PermGroupOps.MovedPoints(g)));
  m:=Apply([1..Length(l)-1],i->0);
  for i in ConjugacyClasses(g) do
    if i.representative<>() then
      m[Position(l,CycleStructurePerm(i.representative))-1]:=1;
    fi;
  od;
  return m;
end;

NumBol := function(b)
  if b then return 1;
       else return 0;
  fi;
end;

SetOrbits := function(g,n)
  return Orbits(g,Combinations(PermGroupOps.MovedPoints(g),n),
                OnSets);
end; 

SeqOrbits := function(g,n)
  return Orbits(g,Arrangements(PermGroupOps.MovedPoints(g),n),
                OnTuples);
end; 

OnSetSets := function(e,g)
  return Set(Apply(e,i->OnSets(i,g)));
end;

OnSetTuples := function(e,g)
  return Apply(e,i->OnSets(i,g));
end;

OnTupleSets := function(e,g)
  return Set(Apply(e,i->OnTuples(i,g)));
end;

OnTupleTuples := function(e,g)
  return Apply(e,i->OnTuples(i,g));
end;

SetSetOrbits := function(g,m)
local p,d;
  p:=PermGroupOps.MovedPoints(g);
  if m>Length(p)/2 then
    Error("too long");
  fi;
  d:=Union(Apply(Combinations(p,m),
             i->Set(Apply(Combinations(Difference(p,i),m),j->Set([i,j])))));
  return Orbits(g,d,OnSetSets);
end;

OrbNEq := function(a,b)
local i;
  for i in a do
    Sort(i);
  od;
  for i in b do
    Sort(i);
  od;
  Sort(a);
  Sort(b);
  return a<>b;
end;
 
CntOp := function(grp,orb,op)
local l,i;
  l:=[];
  for i in orb do
    Add(l,SignPermGroup(Operation(grp,i,op))*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;

TransitiveIdentification := function(ogrp)
local dom,p,s,t,a,cand,i,grp,deg;
  grp:=ogrp;
  if IsBound(grp.transitiveType) then
    return grp.transitiveType;
  fi;
  dom:=PermGroupOps.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
    cand:=Filtered(cand,
     i->TRANSProperties(deg,i)[6]
        =CntOp(grp,Orbits(grp,Combinations(dom,2),OnSets),OnSets)
     and TRANSProperties(deg,i)[7]
        =CntOp(grp,Orbits(grp,Arrangements(dom,2),OnTuples),OnTuples)
     and TRANSProperties(deg,i)[8]
        =CntOp(grp,Orbits(grp,Combinations(dom,3),OnSets),OnSets) );
  fi;

  if Length(cand)>1 and IsSolvable(grp) then
    t:=[];
    a:=AgGroup(grp);
    for i in ConjugacyClasses(a) do
      s:=ConjugacyClass(grp,Image(a.bijection,i.representative));
      s.centralizer:=Image(a.bijection,i.centralizer);
      Add(t,s);
    od;
    grp.conjugacyClasses:=t;
  fi;

  if Length(cand)>1 then
    s:=Apply(CycleStructures(grp),i->i=1);
    cand:=Filtered(cand,i->TRANSProperties(deg,i)[5]=s);
  fi;
  if Length(cand)>1 then
    p:=Apply(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:=Apply(p,i->Collected(Apply(AllBlocks(i),Length)));
    s:=Collected(Apply(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,SetOrbits(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 then
    # As all computations, which follow involve only the groups, convert
    # them to AgGroups if possible
    if IsSolvable(grp) then
      s:=Filtered([1..Length(cand)],i->IsSolvable(p[i]));
      cand:=cand{s};

      grp:=AgGroup(grp);
      grp.bij:=grp.bijection;
      p:=Apply(p{s},AgGroup);
      for s in p do 
        s.bij:=s.bijection;
      od;
    else
      grp.bij:=IdentityMapping(grp);
      for s in p do 
        s.bij:=IdentityMapping(s);
      od;
    fi;


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

  if Length(cand)>1 then
    # NormalSubgroups
    t:=Collected(Apply(NormalSubgroups(grp),Size));
    s:=Filtered([1..Length(cand)],
                i->Collected(Apply(NormalSubgroups(p[i]),Size))=t);
    cand:=cand{s};
    p:=p{s};
  fi;  

  if Length(cand)>1 and Size(grp)<10000 then
    # Subgroups
Print("Subgroups ",cand,"\n");
    t:=Collected(Apply(ConjugacyClassesSubgroups(grp),
                      i->[Size(i.representative),Size(i)]));
    s:=Filtered([1..Length(cand)],i->Collected(Apply(
           ConjugacyClassesSubgroups(p[i]),
           i->[Size(i.representative),Size(i)]))=t);
    cand:=cand{s};
    p:=p{s};
  fi;  

  if Length(cand)>1 then
    # now finally the hard test: Test for conjugacy
Print("Conjugacy Test",cand,"\n");
    s:=SymmetricPermGroup(Maximum(dom));
    if IsSolvable(grp) then
      grp:=grp.bijection.range;
      p:=Apply(p,i->i.bijection.range);
    fi; 
    grp:=AsSubgroup(s,grp);
    p:=Apply(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
    ogrp.transitiveType:=cand[1];
    return cand[1];
  else
    Error("Uh-Oh, this should never happen ",cand);
  fi;
end;

#############################################################################
##
#F  SelectTransitiveGroups(arglis,alle)  . . . . . selection function
##
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:=[1..TRANSDEGREES];
  p:=Position(arglis,DegreeOperation);
  if p<>false 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;
  p:=[];
  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<>false then
    a:=arglis[a+1];
    for i in Filtered(deg,i->i>15 and not IsPrime(i)) do
      if IsFunc(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;

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

    # get all cheap properties first
    if a=DegreeOperation 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;
      if IsInt(b) then
        b:=[b];
      fi;
      for i in deg do
        if IsList(b) then
          gut[i]:=Filtered(gut[i],j->TRANSProperties(i,j)[nr] in b);
        else
          gut[i]:=Filtered(gut[i],j->b(TRANSProperties(i,j)[nr]));
        fi;
      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;
    else
      if not IsList(b) then
        b:=[b];
      fi;
      Add(p,[a,b]); 
    fi;
  od;

  if f then
    Print("#W  AllTransitiveGroups: Degree restricted to [1..",
          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->i[1](g) in 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
##
AllTransitiveGroups := function ( arg )
  return SelectTransitiveGroups(arg,true);
end;

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

