# Companion program to the paper: ``On transitive Permutation Groups''.

# This file (which runs in GAP 3.4.4, (see
# http://www-gap.dcs.st-and.ac.uk/~gap for details how to get it)
# has essentially been used to produce the lists of groups in the
# appendix. (Further hand editing is needed to make the page breaks look
# nice.) The function 
#
# PrintPerms(list)
#
# takes a list of transitive permutation groups of the same degree and
# prints a TeX file similar to the one in the appendix by computing the
# appropriate informations. (As there is no
# function `TwoClosure' in the release this version prints 0 as the
# identification number).

# Calling 
# PrintTo("filename",PrintPerms(list));
# will redirect all output to the file filename.

# The GAP command
# l:=AllTransitiveGroups(DegreeOperation,n);
# will create a list of all transitive groups of degree n (n<=15). It is
# possible to give further restrictions to get only groups with certain
# properties (see the manual for details).

# Alexander Hulpke, 7-May-1998

#############################################################################
##
#F  MyStringPerm( <perm> )  . . . . . . . . convert permutation into a string
##
MyStringPerm := function( perm,deg )
local   str,i,yet;

  if perm = perm ^ 0 then
    str := "()";
  else
    str := "";
    i:=deg;
    yet:=[];
    while Length(yet)<deg-1 do
      Add(yet,i);
      if i^perm<>i then
	str:=ConcatenationString(str,"(");
	if i<deg then
	  str:=ConcatenationString(str, StringInt( i ) );
	else
	  str:=ConcatenationString(str,"0");
	fi;
	i:=i^perm;
	while not i in yet do
	  Add(yet,i);
	  str:=ConcatenationString(str,",",StringInt(i));
	  i:=i^perm;
	od;
	str:=ConcatenationString( str,")");
      fi;
      i:=1;
      while i in yet do
	i:=i+1;
      od;
    od;
  fi;
  return str;
end;

LettStr:="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
LettStr2:="bcdefghijkmnpqstuwxzABCDEFGHIKLMNOPRUVWXZ";
LetterNr:=function(nr)
  if nr<=52 then
    return LettStr{[nr]};
  elif nr<=78 then
    return Concatenation("{\\cal ",LettStr{[nr-26]},"}");
  else
    return Concatenation("{\\frak ",LettStr2{[nr-78]},"}");
  fi;
end;

TeXName:=function(s)
local l,t,d,f,digits;
  digits:="0123456789";
  l:=Length(s);
  t:="$";
  while l>0 do
    d:=1;
    f:=false;
    if l>4 and s{[1..5]}="1/360" then
      t:=Concatenation(t,"\\frac1{360}");
      d:=5;
    elif l>4 and s{[1..5]}="1/720" then
      t:=Concatenation(t,"\\frac1{720}");
      d:=5;
    elif l>2 and s{[1..3]}="1/2" then
      t:=Concatenation(t,"\\frac12");
      f:=true;
    elif l>2 and s{[1..3]}="1/3" then
      t:=Concatenation(t,"\\frac13");
      f:=true;
    elif l>2 and s{[1..3]}="1/4" then
      t:=Concatenation(t,"\\frac14");
      f:=true;
    elif l>2 and s{[1..3]}="1/5" then
      t:=Concatenation(t,"\\frac15");
      f:=true;
    elif l>2 and s{[1..3]}="1/6" then
      t:=Concatenation(t,"\\frac16");
      f:=true;
    elif l>2 and s{[1..3]}="1/7" then
      t:=Concatenation(t,"\\frac17");
      f:=true;
    elif l>2 and s{[1..3]}="1/8" then
      t:=Concatenation(t,"\\frac18");
      f:=true;
    elif l>2 and s{[1..3]}="1/9" then
      t:=Concatenation(t,"\\frac19");
      f:=true;
    elif l>2 and s{[1..3]}=" = " then
      t:=Concatenation(t,"$\\\\\n$=");
      d:=3;
    elif l>1 and s{[1..2]}="wr" then
      t:=Concatenation(t,"\\wr ");
      d:=3;
    elif s[1]=':' then
      t:=Concatenation(t,"{:}");
    elif s[1]='x' then
      t:=Concatenation(t,"{\\times}");
    elif s[1]='{' then
      t:=Concatenation(t,"\\{");
    elif s[1]='}' then
      t:=Concatenation(t,"\\}");
    elif s[1]='%' then
      t:=Concatenation(t,"\\div ");
    elif s[1]='`' then
      t:=Concatenation(t,"{\\hidot}");
    elif s[1] in digits then
      d:=1;
      while Length(s)>d and s[d+1] in digits do
	d:=d+1;
      od;
      if d>1 then
	Add(t,'{');
      fi;
      t:=Concatenation(t,s{[1..d]});
      if d>1 then
	Add(t,'}');
      fi;
    else
      Add(t,s[1]);
    fi;
    if f then
      # get rid of . after frac
      if l>3 and s[4]='.' then
	d:=4;
      else
	d:=3;
      fi;
    fi;
    if d<l then
      s:=s{[d+1..l]};
    fi;
    l:=l-d;
  od;
  Add(t,'$');
  IsString(t);
  return t;
end;

TeXFactors:=function(n)
local s,f,z,i;
  s:="$";
  f:=Collected(Factors(n));
  z:=false;
  for i in f do
    if z then
      s:=Concatenation(s,"{\\cdot}");
    fi;
    s:=Concatenation(s,String(i[1]));
    if i[2]=1 then
      z:=true;
    else
      z:=false;
      s:=Concatenation(s,"^{",String(i[2]),"}");
    fi;
  od;
  Add(s,'$');
  IsString(s);
  return s;
end;

PrintPerms:=function(l)
local deg,i,f,f2,g,j,prms,pool,bpool,blcks,prods,prodnames,p,b,par,ln,sy,mp,lim;
  lim:=1;
  Print("\\documentstyle[amsfonts]{article}\n");
  #Print("\\usepackage[amsfonts]\n");
  Print("\\marginparwidth 0pt\\marginparsep 0pt\n");
  Print("\\evensidemargin 0pt\\oddsidemargin 0cm\n");
  Print("\\textwidth=21.6cm\\textheight=14cm\n");
  Print("\\def\\hidot{{}^\\cdot}\n");
  Print("\\def\\ra{\\kern.45em}\n");
  Print("\\def\\myfrac#1#2{\\hbox{\\kern.1em\n");
  Print("\\raise.5ex\\hbox{\\scriptsize #1}\\kern -.1em\n");
  Print("/\\kern-.15em\\lower.25ex\\hbox{\\scriptsize #2}}}\n");
  Print("\\def\\gen#1{\\left\\langle#1\\right\\rangle}\n");
  Print("\\begin{document}\n");
  Print("\\pagestyle{empty}\n\n");
  par:="- +";
  deg:=Length(PermGroupOps.MovedPoints(l[1]));
  Print("\\noindent{\\Large\\bf Degree ",deg,":}\n\\bigskip\\\\\n");
  sy:=SymmetricGroup(deg);
  bpool:=[];
  blcks:=[];
  for i in l do
    if not IsBound(i.zeroBlocks) then
      g:=AllBlocks(i);
      f:=[];
      for j in g do
	Add(f,First(Blocks(i,[1..deg],j),i->deg in i));
      od;
      i.zeroBlocks:=f;
    fi;
    blcks:=Concatenation(blcks,i.zeroBlocks);
  od;

  f:=Filtered(Collected(blcks),i->i[2]>1);
  Sort(f,function(a,b) if Length(a[1])=Length(b[1]) then return a[2]>b[2];
                       else return Length(a[1])<Length(b[1]);fi;end);
  blcks:=[];
  bpool:=[];
  j:=0;
  for i in f do
    Add(bpool,i[1]);
    if Length(i[1])>j then
      j:=Length(i[1]);
      g:=0;
    else
      g:=g+1;
    fi;
    f2:=String(Length(i[1]));
    if g>0 then
      f2:=ConcatenationString(f2,LetterNr(g));
    fi;
    Add(blcks,[i[1],f2]);
  od;

  prms:=Collected(Flat(List(l,i->i.generators)));

  # sort by usage frequency
  prms:=List(prms,i->[i[2],i[1]]);
  Sort(prms);
  prms:=Reversed(prms);
  prms:=List(prms,i->[i[2],i[1]]);

  pool:=List(Filtered(prms,i->i[2]>lim),i->i[1]);
  prms:=List(Filtered(prms,i->i[2]<=lim),i->i[1]);
  # search for products
  prods:=[];
  prodnames:=[];
  for i in prms do
    for j in pool do
      f:=false;
      if i/j in pool then
	f:=Concatenation(LetterNr(Position(pool,i/j)),#"{\\cdot}",
			 LetterNr(Position(pool,j)));
      elif i*j in pool then
	f:=Concatenation(LetterNr(Position(pool,i*j)),"/",
			 LetterNr(Position(pool,j)));
      elif j*i in pool then
	f:=Concatenation(LetterNr(Position(pool,j)),"^{-1}",
			 LetterNr(Position(pool,j*i)));
      fi;
      if f<>false then
	p:=Position(prods,i);
	if p=false then
	  Add(prods,i);
	  Add(prodnames,f);
	elif '/' in prodnames[p] or '-' in prodnames[p] and
	     not ('/' in f or '-' in f) then
	  prodnames[p]:=f;
	fi;
      fi;
    od;
  od;

  Print("{\\bf Generators:}\n");
  Print("\\begin{eqnarray*}");
  for i in [1..Length(pool)] do
    Print(LetterNr(i),"&=&",MyStringPerm(pool[i],deg),"\\\\\n");
  od;
  Print("\\end{eqnarray*}");

  if Length(blcks)>0 then
    Print("\n");
    Print("{\\bf Blocks:}\n");
    Print("\\begin{eqnarray*}");
    for i in blcks do
      f:=Concatenation([0],Filtered(i[1],j->j<deg));
      Print(i[2],"&=&",f,"\\\\\n");
    od;
    Print("\\end{eqnarray*}");
  fi;

  Print("\n");

  ln:=0;

  for i in [1..Length(l)] do

    if ln=0 then
      Print("\\noindent\\begin{tabular}%\n",
      "{r@{\\ra}l@{\\ra}l@{\\ra}c@{\\ra}r@{\\ra}r@{\\ra}l@{\\ra}l@{\\ra}l}\n");
      Print("Nr&Name&$\\left|G\\right|$&p&N&C&S&Generators&Blocks\\\\\n");
      Print("\\hline\n");
    fi;

    g:=l[i];
    Print("\\vphantom{\\Large(}\n");
    Print(i,"&\\begin{minipage}[t]{20mm}\n",TeXName(g.name),
	   "\n\\end{minipage}\n&");
    f:=Size(g);
    if f=Factorial(deg) then
      f2:=ConcatenationString("$",String(deg),"!$");
    elif 2*f=Factorial(deg) then
      f2:=ConcatenationString("$\\frac{",String(deg),"!}2$");
    else 
      f2:=TeXFactors(f);
    fi;
    if not IsBound(g.symmnormalizer) then
      f:=Normalizer(sy,AsSubgroup(sy,g));
    else
      f:=g.symmnormalizer;
    fi;
    Print(Size(g),"=",f2,"&$",par{[SignPermGroup(g)+2]},"$&",
	  TransitiveIdentification(f),"&");
    # the TwoClosure command is not available in the official GAP 3.4.4
    #Print(TransitiveIdentification(TwoClosure(g)),"&\n");
    Print("0&\n");

    # point stabilizer actions
    f:=Stabilizer(g,deg);
    mp:=Filtered(Orbits(f,[1..deg-1]),i->Length(i)>1);
    mp:=List(mp,i->[Length(i),TransitiveIdentification(Operation(f,i))]);
    mp:=Collected(mp);
    for j in mp do
      Print("${\\myfrac{",j[1][1],"}{",j[1][2],"}}");
      if j[2]>1 then
        Print("^{",j[2],"}");
      fi;
      Print("$%\n");
    od;
    Print("&\n");

    f:=false;
    f2:=false;
    mp:=Number(g.generators,i->not(i in pool or i in prods))>1;
    if mp then
      Print("\\begin{minipage}[t]{3cm}\\begin{flushleft}\n");
    fi;
    for j in g.generators do
      if f then
	Print(",");
      fi;
      if f2 then
	Print("\n");
      fi;
      f:=true;
      p:=Position(pool,j);
      f2:=false;
      if p<>false then
	Print("$",LetterNr(p),"$");
      else
	p:=Position(prods,j);
	if p<>false then
	  Print("$",prodnames[p],"$");
	else
	  Print(" $",MyStringPerm(j,deg),"$");
	  f2:=true;
	fi;
      fi;
    od;
    if mp then
      Print("\n\\end{flushleft}\\end{minipage}");
    fi;
    Print("&\n");
    f:=false;
    #if Length(g.zeroBlocks)=0 then
      #Print("p");
    #fi;
    for j in g.zeroBlocks do
      if f then
	Print(",");
      fi;
      f:=true;
      p:=Position(bpool,j);
      if p<>false then
	Print(blcks[p][2]);
      else
	j:=Blocks(g,[1..deg],j);
	j:=First(j,i->deg in i);
	j:=Union([0],Filtered(j,i->i<>deg));
	j:=Filtered(String(j),i->not i in " ");
	IsString(j);
	Print(j);
      fi;
    od;
    Print("\\\\\n");
    ln:=ln+1+Number(g.name,i->i='=');
    if ln>27 then
      ln:=0;
      Print("\\end{tabular}\n\n");
    fi;
  od;
  if ln>0 then
    Print("\\end{tabular}\n\n");
  fi;
  Print("\\end{document}\n\n");
end;