Genere:=function(m,d)
return d*(-2+#m-&+[1/m[i]: i in [1..#m]])/2+1;
end function;


PossibiliSegnature:=function(d,r,g)
L:=[];
T:=[];
X:=Remove(Divisors(d),1);
x:=#X;
b:=Binomial(r+x-1,r);
for j in [1..r] do
	T[j]:=x;
end for;
if Genere(X[T],d) eq g then
	Append(~L,X[T]);
end if;

for i in [2..b] do
	for j in [1..r] do
		if T[j] gt 1 then
			T[j]:=T[j]-1;
			for k in [1..j-1] do
				T[k]:=T[j];
			end for;
			if Genere(X[T],d) eq g then
				Append(~L,X[T]);
			end if;
			break;
		end if;
	end for;
end for;
return Sort(L);
end function;


Treccia:=function(t,i)
return Insert(Remove(t,i),i+1,t[i]^t[i+1]);
end function;

TrecciaInversa:=function(t,i)
return Insert(Remove(t,i+1),i,t[i+1]^(t[i]^-1));
end function;


GeneratoriSferici:=function(G,m,ElGOrd)
r:=#m;
P:=CartesianProduct([ElGOrd[m[i]]: i in [1..r-1]]);
S:={};
Generano:={};
NonGenerano:={};
for x in P do
	y:=&*x;
	if y in ElGOrd[m[r]] then
		t:=Append([g:g in x],y^-1);
		s:=Set(t);
		if s in Generano then
			Include(~S,t);
		else 
			if s in NonGenerano then
				continue x;
			else
				if #sub<G|s> eq #G then 
					Include(~Generano,s);
					Include(~S,t);
				else
					Include(~NonGenerano,s);
				end if;
			end if;
		end if;
	end if;
end for;

if IsEmpty(S) then
	return [];
end if;

Sn:=Sym(S);
genGruppone:={};
A:=AutomorphismGroup(G);

for phi in Generators(A) do
	prod:=Sn!1;
	N:={};
	for x in S do
		y:=phi(x);
		if y notin N and y ne x then
			Include(~N,x);
			prod:=Sn!(x,y)*prod;
		end if;
	end for;
	Include(~genGruppone,prod);
end for;

im:=[i: i in [1..r-1] | m[i] eq m[i+1]];

if IsAbelian(G) then
	for i in im do
		prod:=Sn!1;
		N:={};
		for x in [x: x in S | x[i] ne x[i+1]] do
			y:=Insert(Remove(x,i),i+1,x[i]);
			if y notin N and y ne x then
				Include(~N,x);
				prod:=Sn!(x,y)*prod;
			end if;
		end for;
		Include(~genGruppone,prod);
	end for;
else
	for i in im do
		prod:=Sn!1;
		N:={};
		for x in S do		
			y:=Treccia(x,i);
			if y notin N and y ne x then
				Include(~N,x);
				prod:=Sn!(x,y)*prod;
			end if;
		end for;
		Include(~genGruppone,prod);
	end for;

	for i in [1..r-1] do
		for j in [i+1..r] do
			if m[i] ne m[j] then
				prod:=Sn!1;
				N:={};
				for x in S do
					y:=x;
					for k in [-(j-1) .. -(i+1)] do
						y:=TrecciaInversa(y,-k);
					end for;
					y:=Treccia(Treccia(y,i),i);
					for k in [i+1 .. j-1] do
						y:=Treccia(y,k);
					end for;

					if y notin N and y ne x then
						Include(~N,x);
						prod:=Sn!(x,y)*prod;
					end if;
				end for;
				Include(~genGruppone,prod);
			end if;
		end for;
	end for;
end if;

H:=sub<Sn|genGruppone>;
Orbite:=OrbitRepresentatives(H);
L:=[rapp[2]: rapp in Orbite];

return L;
end function;



PossibiliGeneratori:=function(d,m)
DatoCpt := recformat< Gruppo, Theta, Sigme>;
ListaDatiCpt:=[];
m2:=Set(Append(m,2));
r:=#m;

NumGr:=NumberOfSmallGroups(d);
for i in [1..NumGr] do
	G:=SmallGroup(d,i);
	try
		numInv:=#AQInvariants(G);
		if numInv gt r then
			continue i;
		end if;
	catch e;
	end try;
	ElGOrd:=[];
	for n in m2 do
		ElGOrd[n]:=[];
	end for;

	for g in G do
		ordine:=Order(g);
		if ordine in m2 then
			Append(~ElGOrd[ordine],g);
		end if;
	end for;

	for n in m2 do
		if IsEmpty(ElGOrd[n]) then
			continue i;
		end if;
	end for;

	ElCentOrd2:=[];
	for g in ElGOrd[2] do
		if IsCentral(G,g) then
			Append(~ElCentOrd2,g);
		end if;
	end for;
	if IsEmpty(ElCentOrd2) then
		continue i;
	end if;

	L:=GeneratoriSferici(G,m,ElGOrd);
	if IsEmpty(L) then
		continue i;
	end if;

	Append(~ListaDatiCpt,rec<DatoCpt| Gruppo:=G, Theta:=L, Sigme:=ElCentOrd2>);
end for;

return ListaDatiCpt;
end function;


GeneraDati:=function(g,r:maxOrd:=r eq 4 select 12*(g-1) else Floor(4*(g-1)/(r-4)))

RF := recformat< OrdG : Integers(), Rami : SeqEnum >;
ListaSegnature:=[];
for d in [2..maxOrd] do
	if IsPrime(d) and d gt 2 then
		continue d;
	end if;
	L:=PossibiliSegnature(d,r,g);
	for m in L do
		Append(~ListaSegnature,rec< RF | OrdG:= d, Rami := m>);
	end for;
end for;

Dato := recformat< G , t , s  >;
ListaDati:=[];
for dxm in ListaSegnature do
	LDC:=PossibiliGeneratori(dxm`OrdG,dxm`Rami);
	for Cpt in LDC do
		for theta in Cpt`Theta do
			for sigma in Cpt`Sigme do
				Append(~ListaDati,rec<Dato|G:=Cpt`Gruppo,t:=theta,s:=sigma>);
			end for;
		end for;
	end for;
end for;

return ListaDati;
end function;


RamificazionePrym:=function(G,t,s)
return Integers()!&+[s in sub<G|x> select #G/Order(x) else 0: x in t];
end function;


OrdiniGeneratori:=function(t)
return [Order(t[j]) : j in [1..#t]];
end function;


MolteplRappH0K:=function(G,t)
T:=CharacterTable(G);
m:=OrdiniGeneratori(t);
K<csi>:=CyclotomicField(#G);
S<x>:=PolynomialRing(K);
Z:=Integers();

//E[k][i][alpha] è la molteplicità dell'autovalore z^alpha di rho_chi(t[i]), dove z=exp(2%pi%i/m[i]) e chi=T[k] è il k-esimo carattere irriducibile.
E:=[];
for k:=1 to #T do
	chi:=T[k];
	n:=Z!chi[1];
	E[k]:=[];
	for i:=1 to #m do
		h:=t[i];
		z:=csi^Z!(#G/m[i]);
		c:=[];
		for l in [1..n] do
			c[l]:=chi(h^l);
			for j in [1..l-1] do
				c[l]+:=c[l-j]*chi(h^j);
			end for;
			c[l]/:=-l;
		end for;

		P:=x^n + &+[K!c[l]*x^(n-l): l in [1..n]];

		E[k][i]:=[0:alpha in [1..m[i]-1]];
		for alpha:=1 to m[i]-1 do
			for l:=1 to Degree(P) do
				if Evaluate(P,z^alpha) eq 0 then
					E[k][i][alpha]+:=1;
					P:=P/(x-z^alpha);
				else
					continue alpha;
				end if;
			end for;
		end for;//alpha
	end for;//i
end for;//k

mu:=[];
for k:=1 to #T do
	mu[k]:=-T[k][1];
	for i:=1 to #m do
		for alpha:=1 to m[i]-1 do
			mu[k]+:=alpha*E[k][i][alpha]/m[i];
		end for;
	end for;
end for;
mu[1]+:=1;
return mu;
end function;



dimS2VG:=function(G,t)
T:=CharacterTable(G);
mu:=MolteplRappH0K(G,t);
N:=1/(2*Order(G))* &+[ &+[(mu[i]*T[i](x)):i in [1..#T]]^2 + &+[mu[i]*T[i](x^2): i in [1..#T]] : x in G];
return N;
end function;

DatoQuoziente:=function(G,t,s)
H,pr:=quo<G|s>;
return H,pr(t);
end function;

testA:=function(G,t,s)
r:=#t;
H,k:=DatoQuoziente(G,t,s);
Ntilde:=dimS2VG(G,t);
N:=dimS2VG(H,k);

return Ntilde-N eq r-3;
end function;


dimTensorG:=function(G,i,j)
T:=CharacterTable(G);
dim:=1/Order(G)*&+[T[i](x)*T[j](x):x in G];
return Integers()!dim;
end function;

testB1:=function(G,t,s)
T:=CharacterTable(G);
mu:=MolteplRappH0K(G,t);
Vm:=[];

for i:=1 to #T do
	if T[i][1] eq 1 and mu[i] gt 0 and T[i](s) eq -1 then
		Append(~Vm,i);
	end if;
end for;

for i in Vm do
	for j in Vm do
		if dimTensorG(G,i,j) eq 1 then
			if mu[i] eq 1 and mu[j] eq #t-3 then
				return true;
			else
				return false;
			end if;
		end if;
	end for;
end for;

return false;
end function;


testStar:=function(G,t)
r:=#[x: x in t | Order(x) gt 1];
return dimS2VG(G,t) eq r-3;
end function;


testB2:=function(G,t,s)
T:=CharacterTable(G);
H10:=MolteplRappH0K(G,t);
V:={i:i in [1..#T]|H10[i] gt 0};
Vp:={};
for i in V do
	if T[i](s) ne T[i][1] then
		continue i;
	end if;
	Include(~Vp,i);
end for;
Vm:=V diff Vp;

for sub in NormalSubgroups(G) do
	if sub`order eq #G then continue sub; end if;
	K:=sub`subgroup;
	for x in t do
		if x in K then
			continue sub;
		end if;
	end for;

	VK:={};
	GK:=Generators(K);
	for i in V do
		for x in GK do
			if T[i](x) ne T[i][1] then
				continue i;
			end if;
		end for;
		Include(~VK,i);
	end for;

	if VK notsubset Vm then
		continue sub;
	end if;
	
	Q,u:=DatoQuoziente(G,t,K);
	if testStar(Q,u) then
		return true;
	end if;
end for;
return false;
end function;



TrovaEsempi_A:=function(g,r)
EsempiEtale:=[];
EsempiRamif:=[];
B:={};
for dato in GeneraDati(g,r) do
	G:=dato`G;
	t:=dato`t;
	s:=dato`s;
	if testA(G,t,s) then
		b:=RamificazionePrym(G,t,s);
		if b eq 0 then
			Include(~B,b);
			Append(~EsempiEtale,dato);
		else 
			if b notin B then
				Include(~B,b);
				EsempiRamif[b]:=[];
			end if;
			Append(~EsempiRamif[b],dato);
		end if;
	end if;
end for;

return EsempiEtale,EsempiRamif,B;
end function;


