Dear Arsene Galstyan, Dear GAP-Forum,
For positive integers n and k, the DESIGN package function call
SemiLatinSquareDuals(n,k) returns a list of the duals of a complete list
of isomorphism class representatives of the (n x n)/k semi-Latin squares,
such that two such squares are considered to be isomorphic if one can
be obtained from the other by a combination of renaming symbols, row
permutations, column permutations, and transposing. Thus, the isomorphism
class of a semi-Latin square S (with symbol set [1..n*k]) whose dual
is obtained from a call to SemiLatinSquareDuals(n,k) is the orbit of
S under the group generated by symbol permutations, row permutations,
column permutations, and transposing.
I've done this as shown in the appended log-file, obtaining the
correct numbers of Latin squares of orders 3, 4, and 5.
There are, however, much more efficient ways to find the *number* of
Latin squares of order n if you are just interested in the number rather
than all the Latin squares themselves.
By the way, for a block design B in the DESIGN package, the component
B.autSubgroup, if bound, is guaranteed to be a subgroup of the
(full) automorphism group of B.
Best wishes,
Leonard
---------------------------------------------------------------
gap>
gap> LoadPackage("design");
-----------------------------------------------------------------------------
Loading GRAPE 4.7 (GRaph Algorithms using PErmutation groups)
by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~leonard/).
Homepage: http://www.maths.qmul.ac.uk/~leonard/grape/
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
Loading DESIGN 1.6 (The Design Package for GAP)
by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~leonard/).
Homepage: http://www.designtheory.org/software/gap_design/
-----------------------------------------------------------------------------
true
gap>
gap> SemiLatinSquareFromDual := function(D)
> local n,S,names,i,pt;
> n:=Length(D.blocks[1]);
> S:=List([1..n],x->List([1..n],y->[]));
> names:=D.pointNames;
> for i in [1..Length(D.blocks)] do
> for pt in D.blocks[i] do
> Add(S[names[pt][1]][names[pt][2]],i);
> od;
> od;
> return S;
> end;
function( D ) ... end
gap>
gap> OnSemiLatinSquares := function(S,g)
> # Returns the image T of the (n x n)/k semi-Latin square S under g,
> # where g acts by permuting the symbols [1..n*k], the rows
> # (labelled [n*k+1..n*k+n]) and the columns (labelled [n*k+n+1..n*k+2*n]),
> # and then possibly transposing the semi-Latin square.
> local n,k,i,j,newposition,T;
> n:=Length(S[1]);
> k:=Length(S[1][1]);
> T:=List([1..n],i->[]);
> for i in [1..n] do
> for j in [1..n] do
> newposition:=OnSets([i+n*k,j+n*k+n],g);
> T[newposition[1]-n*k][newposition[2]-n*k-n]:=OnSets(S[i][j],g);
> od;
> od;
> return T;
> end;
function( S, g ) ... end
gap>
gap> SemiLatinSquareIsomorphismClass := function(S)
> # Returns the full (weak) isomorphism class of the (n x n)/k
> # semi-Latin square S.
> local n,k,transposer,g_symbols,g_rows,g_columns,G,i;
> n:=Length(S[1]);
> k:=Length(S[1][1]);
> transposer:=Product(List([n*k+1..n*k+n],i->(i,i+n)));
> g_symbols:=GeneratorsOfGroup(SymmetricGroup([1..n*k]));
> g_rows:=GeneratorsOfGroup(SymmetricGroup([n*k+1..n*k+n]));
> g_columns:=GeneratorsOfGroup(SymmetricGroup([n*k+n+1..n*k+2*n]));
> G:=Group(Concatenation(g_symbols,g_rows,g_columns,[transposer]));
> return Set(Orbit(G,S,OnSemiLatinSquares));
> end;
function( S ) ... end
gap>
gap> n:=3;
3
gap> duals:=SemiLatinSquareDuals(n,1);;
gap> squares:=List(duals,SemiLatinSquareFromDual);
[ [ [ [ 1 ], [ 2 ], [ 3 ] ], [ [ 3 ], [ 1 ], [ 2 ] ], [ [ 2 ], [ 3 ], [ 1 ] ]
] ]
gap> classes:=List(squares,SemiLatinSquareIsomorphismClass);;
gap> L:=List(classes,Length);
[ 12 ]
gap> Sum(L);
12
gap>
gap> n:=4;
4
gap> duals:=SemiLatinSquareDuals(n,1);;
gap> squares:=List(duals,SemiLatinSquareFromDual);
[ [ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ], [ [ 4 ], [ 1 ], [ 2 ], [ 3 ] ],
[ [ 3 ], [ 4 ], [ 1 ], [ 2 ] ], [ [ 2 ], [ 3 ], [ 4 ], [ 1 ] ] ],
[ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ], [ [ 2 ], [ 1 ], [ 4 ], [ 3 ] ],
[ [ 3 ], [ 4 ], [ 1 ], [ 2 ] ], [ [ 4 ], [ 3 ], [ 2 ], [ 1 ] ] ] ]
gap> classes:=List(squares,SemiLatinSquareIsomorphismClass);;
gap> L:=List(classes,Length);
[ 432, 144 ]
gap> Sum(L);
576
gap>
gap> n:=5;
5
gap> duals:=SemiLatinSquareDuals(n,1);;
gap> squares:=List(duals,SemiLatinSquareFromDual);
[ [ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ],
[ [ 5 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ] ],
[ [ 4 ], [ 5 ], [ 1 ], [ 2 ], [ 3 ] ],
[ [ 3 ], [ 4 ], [ 5 ], [ 1 ], [ 2 ] ],
[ [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 1 ] ] ],
[ [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ],
[ [ 3 ], [ 1 ], [ 5 ], [ 2 ], [ 4 ] ],
[ [ 5 ], [ 4 ], [ 1 ], [ 3 ], [ 2 ] ],
[ [ 2 ], [ 5 ], [ 4 ], [ 1 ], [ 3 ] ],
[ [ 4 ], [ 3 ], [ 2 ], [ 5 ], [ 1 ] ] ] ]
gap> classes:=List(squares,SemiLatinSquareIsomorphismClass);;
gap> L:=List(classes,Length);
[ 17280, 144000 ]
gap> Sum(L);
161280
gap>
On Fri, Jul 22, 2016 at 12:56:41PM +0300, Arsene Galstyan wrote:
>
>
> Dear GAP forum,
>
> I'm interested in function SemiLatinSquareDuals(n,k) that is included in
> the package "DESIGN". I would like to know it is possible to use this
> function that to find the number of Latin squares of a given order.
> As it is written in manual, this function " can classify semi-Latin squares
> with certain given properties, and return a list of their duals as block
> designs". Note that (nxn)/1 semi-Latin square (that is, for k = 1) is the
> same thing as a Latin square of order n.
> Thus, for k=1, function breaks set of Latin square of order n on the set
> non-isomorphic classes. Each record resulting list corresponds exactly to one
> of his class. For n=3, it returns the following:
>
> gap> SemiLatinSquareDuals(3,1);
> [ rec( autSubgroup := Group([ (2,4)(3,7)(6,8), (2,3)(4,7)(5,9)(6,8), (1,5,9)
> (2,6,7)(3,4,8), (1,4,7)(2,5,8)(3,6,9) ]), blockNumbers := [ 3 ],
> blockSizes := [ 3 ], blocks := [ [ 1, 5, 9 ], [ 2, 6, 7 ], [ 3, 4, 8 ] ]
> , isBinary := true, isBlockDesign := true, isSimple := true,
> pointNames := [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ],
> [ 2, 3 ], [ 3, 1 ], [ 3, 2 ], [ 3, 3 ] ], r := 1,
> tSubsetStructure := rec( lambdas := [ 1 ], t := 1 ), v := 9 ) ]
>
> That is, as I understand it, exist only one isomorphic class, i.e. the set of
> all Latin square of order 3 is one class. In other words, all Latin square of
> order 3 are pairwise isomorphic. That is, one can be obtained from the other
> by using composite of permutations of rows, columns and transposition
> operations.
> If I understand correctly, field "autSubgroup" is permutation subgroup
> which is a group of automorphisms of a class of Latin squares corresponding
> to this record. That is, each element of this group carries permutations of
> rows, or(and) columns, or(and) transposition of Latin square.
> In this way, as I think, you can act on one element of this class by all
> elements of the group of automorphisms of this class in course and get all
> the elements of the class, i.e., all Latin squares of order 3.
> Field "blocks" is binary block design, which dual of Latin square (with the
> first row is ordered), which belongs to the class of Latin squares
> corresponding to this record. As I understand, the square can be recovered
> from the block design in the following way. i-th block of block design
> corresponding i-th symbol of Latin square and each point of block design
> represents number of cells of Latin square.
> In this way, it is possible to write a function that transforms a block
> design of each record in the Latin square, corresponding to it, and then acts
> on each obtained square of all permutations of automorphism group that
> corresponds to him.
>
> This is text of function "ConclusionSquares":
>
> Print("Load 'ConclusionSquares(n)'","\n");
> ConclusionSquares:= function(n)
> local i, j, k, NumberClasses, SLSD, SubsidiaryArray, ListLatinSquares,
> LenList, SZ, permut, NumberRepetition, NumberRepetitionForEach, AutomSquare,
> AutomSquareForEach, NumberLatinSquareForEach;
> SLSD:= SemiLatinSquareDuals(n,1);
> NumberClasses:= Length(SLSD);
> ListLatinSquares:= [ ];
> #conclusion Latin square that corresponding of records
> for i in [1..NumberClasses] do
> ListLatinSquares[i]:= [ ];
> for j in [1..n] do
> for k in [1..n] do
> ListLatinSquares[i][SLSD[i].blocks[j][k]]:= j;
> od;
> od;
> SubsidiaryArray:= [ ];
> for j in [1..n] do
> SubsidiaryArray[j]:= [ ];
> for k in [1..n] do
> SubsidiaryArray[j][k]:= ListLatinSquares[i][n*(j-1) + k];
> od;
> od;
> Print(" ",i,")","\n");
> Display(SubsidiaryArray);
> Print("\n");
> od;
> #count of Latin squares
> LenList:= NumberClasses;
> NumberRepetition:= 0;
> AutomSquare:= 0;
> for i in [1..NumberClasses] do
> permut:= Difference(AsList(SLSD[i].autSubgroup),[()]);
> SZ:= Size(permut);
> NumberLatinSquareForEach:= 1;
> NumberRepetitionForEach:= 0;
> AutomSquareForEach:= 0;
> for j in [1..SZ] do
> SubsidiaryArray:= [ ];
> for k in [1..n*n] do
> SubsidiaryArray[k^permut[j]]:= ListLatinSquares[i][k];
> od;
> if (SubsidiaryArray in ListLatinSquares) then
> NumberRepetitionForEach:= NumberRepetitionForEach + 1; #number
> repetitions for each record
> if (SubsidiaryArray = ListLatinSquares[i]) then
> AutomSquareForEach:= AutomSquareForEach + 1; #number of
> permutetions which not change Latin square
> fi;
> else
> NumberLatinSquareForEach:= NumberLatinSquareForEach + 1; #number
> different Latin square for each record
> LenList:= LenList + 1;
> ListLatinSquares[LenList]:= [ ];
> ListLatinSquares[LenList]:= SubsidiaryArray;
> fi;
> od;
> Print ("[rec #",i,": Number elements in autSubgroup = ",SZ+1,"; Number
> Latin Squares = ",NumberLatinSquareForEach,"; Number repetition =
> ",NumberRepetitionForEach,"; Number automorfisms =
> ",AutomSquareForEach,"]","\n","\n");
> NumberRepetition:= NumberRepetition + NumberRepetitionForEach;
> AutomSquare:= AutomSquare + AutomSquareForEach;
> od;
> #conclusion list of Latin square
> for i in [NumberClasses+1..LenList] do
> SubsidiaryArray:= [ ];
> for j in [1..n] do
> SubsidiaryArray[j]:= [ ];
> for k in [1..n] do
> SubsidiaryArray[j][k]:= ListLatinSquares[i][n*(j-1) + k];
> od;
> od;
> Print(" ",i,")","\n");
> Display(SubsidiaryArray);
> od;
> return ["Length(ListLatinSquares)=",Length(ListLatinSquares),"
> NumberRepetition=",NumberRepetition," AutomSquare=",AutomSquare];
>
> end;
> Function result for n=3:
>
> gap> ConclusionSquares(3);
> 1)
> [ [ 1, 2, 3 ],
> [ 3, 1, 2 ],
> [ 2, 3, 1 ] ]
>
> [rec #1: Number elements in autSubgroup = 36; Number Latin Squares = 6;
> Number repetition =
> 30; Number automorfisms = 5]
>
> 2)
> [ [ 1, 3, 2 ],
> [ 2, 1, 3 ],
> [ 3, 2, 1 ] ]
> 3)
> [ [ 2, 1, 3 ],
> [ 3, 2, 1 ],
> [ 1, 3, 2 ] ]
> 4)
> [ [ 3, 1, 2 ],
> [ 2, 3, 1 ],
> [ 1, 2, 3 ] ]
> 5)
> [ [ 2, 3, 1 ],
> [ 1, 2, 3 ],
> [ 3, 1, 2 ] ]
> 6)
> [ [ 3, 2, 1 ],
> [ 1, 3, 2 ],
> [ 2, 1, 3 ] ]
>
> [ "Length(ListLatinSquares)=", 6, " NumberRepetition=", 30, " AutomSquare=",
> 5 ]
>
> So, we got exactly 6 different squares. But the number of Latin squares of
> order 3 is 12 pieces. Due to the fact that all first rows are different and
> the number is 3 !, there is an idea to mix all the rows from the second to
> last together. That is , multiplied by 2 !. Just get 3 ! * 2 ! = 12 . But
> this idea is crumbling at n=4:
>
> gap> ConclusionSquares(4);
> 1)
> [ [ 1, 2, 3, 4 ],
> [ 4, 1, 2, 3 ],
> [ 3, 4, 1, 2 ],
> [ 2, 3, 4, 1 ] ]
>
> 2)
> [ [ 1, 2, 3, 4 ],
> [ 2, 1, 4, 3 ],
> [ 3, 4, 1, 2 ],
> [ 4, 3, 2, 1 ] ]
>
> [rec #1: Number elements in autSubgroup = 64; Number Latin Squares = 8;
> Number repetition =
> 56; Number automorfisms = 7]
>
> [rec #2: Number elements in autSubgroup = 192; Number Latin Squares =
> 24; Number repetition = 168; Number automorfisms = 7]
>
> [ "Length(ListLatinSquares)=", 32, " NumberRepetition=", 224, "
> AutomSquare=", 14 ]
>
>
> Latin squares of order 4 exactly 576, but 32*3!=192. In this situation , of
> course, you can still guess as from 32 to receive 576 , because 576 divided
> by 32. But if n=5, then
>
> gap> ConclusionSquares(5);
> 1)
> [ [ 1, 2, 3, 4, 5 ],
> [ 5, 1, 2, 3, 4 ],
> [ 4, 5, 1, 2, 3 ],
> [ 3, 4, 5, 1, 2 ],
> [ 2, 3, 4, 5, 1 ] ]
>
> 2)
> [ [ 1, 2, 3, 4, 5 ],
> [ 3, 1, 5, 2, 4 ],
> [ 5, 4, 1, 3, 2 ],
> [ 2, 5, 4, 1, 3 ],
> [ 4, 3, 2, 5, 1 ] ]
>
> [rec #1: Number elements in autSubgroup = 200; Number Latin Squares =
> 20; Number repetition = 180; Number automorfisms = 9]
>
> [rec #2: Number elements in autSubgroup = 24; Number Latin Squares = 24;
> Number repetition =
> 0; Number automorfisms = 0]
>
> [ "Length(ListLatinSquares)=", 44, " NumberRepetition=", 180, "
> AutomSquare=", 9 ]
>
> Latin squares of order 5 exactly 161280 and 161280 is not divisible by 44.
> Therefore , from the number of Latin squares , so that you can get , it is
> impossible to find all the squares of a given order . That is, function
> SemiLatinSquareDuals does not answer the question about the number of Latin
> squares .
> The following questions . Am I right? Did I everything right and
> reasoned? If so, then the function SemiLatinskuare ( n , k) is not working
> properly or I did not understand then what it does .
> By the way, this function has a few optional parameters:
> SemiLatinSquareDuals(n,k,maxmult,blockintsize, isolevel). A ll these
> parameters in this case, for k=1, are not interesting , because we consider
> only Latin squares .
>
> Thank you very much!
>
> Best regards,
>
> Arsene Galstyan
> ares.1...@mail.ru
> _______________________________________________
> Forum mailing list
> Forum@mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
