####################### latinsquares ##### 20.1.2003 ########## ##################################################################### # This is a collection of GAP4-programs used in the paper # # Diagonal-complete latin squares # # by Olaf Krafft, Herbert Pahlings and Martin Schaefer (RWTH-Aachen) # # European J. of Combinatorics, 24 (2003), p.229-237 # # # Questions or suggestions are welcome and should be sent to # Herbert.Pahlings@math.rwth-aachen.de # ####################################################################### ####################################################################### ### Definitions # # Let N = {1,...,n}. # A latin square A = [a_{i,j}] is "right-diagonal-complete" (r-complete) # if { ( a_{i,j} , a_{i+1,j+1} ) | i,j in N } = { (i,j) | i,j in N } . # and "left-diagonal-complete" (l-complete) # if { ( a_{i,j} , a_{i-1,j-1} ) | i,j in N } = { (i,j) | i,j in N } . # Here all indices have to be taken mod n . # # For the purpose of the programmes below these definitions have been # extended to latin rectangles [a_{i,j}] in N^{m x n} with m < n # which are called r-complete if # | { ( a_{i,j} , a_{i+1,j+1} ) | i = 1..m-1 , j = 1..n } | = (m-1)*n , # where again indices have to be taken mod n . Similarly for l-completeness. # # The rows of a latin square A can be considered as permutations: # [a_1,...,a_n] is 'identified' with p = ( i -> a_i ) in S_n . # They generate a transitive subgroup G(A) of S_n . If they form a # subgroup (in other words, if G(A) is regular) then A is said to be # "based on a group". A latin square based on a group G can be given # by listing generators of (the regular permutation group) G and by # by listing the first column, which may be an arbitrary permutation # in S_n . # # We call a latin square "normalized" if its first row is [1.,,,.n] . # We call a latin square based on a group "in normal form" if # the first column is [1,...,n]^T . # ######################################################################## ### Examples ### ### In the following examples lines beginning with # are GAP command-lines ## are GAP output ### are comments. ### Of course, the commands in the examples work only, when (the collection ### of functions of) this file has been read in in a GAP-session. ### ### ### Example 1 (r-complete latin squares of degree 4,5,6,7) ### # n := 4;; # li := Derangements( [1..n] );; # res := latRcomplete( [[1..n]] , li );; # Display( res[1] ); ### computes all (four) r-complete latin squares with first row ### [1,2,3,4] and displays the first one as ## [ [ 1, 2, 3, 4 ], ## [ 2, 1, 4, 3 ], ## [ 4, 3, 2, 1 ], ## [ 3, 4, 1, 2 ] ] # # Set ( List (res , groupLQ ) ); ## [ Group([ (), (1,2)(3,4), (1,4)(2,3), (1,3)(2,4) ]) ] ### All four r-complete latin squares are based on the Klein 4-group # ma := List( Elements( groupLQ(res[1]) ), ListPerm );; ma[1]:=[1..n];; # groupbasedlatRcomplete(ma,[1]); ## [ [ 1, 2, 4, 3 ], [ 1, 3, 2, 4 ], [ 1, 3, 4, 2 ], [ 1, 4, 2, 3 ] ] ### These are the first columns of the four r-complete latin squares with ### first row [1,2,3,4] based on the above group. ### Remark: For n = 5,6,7 the same computations show that no r-complete ### latin square of these sizes exist. For n = 7 this computation already ### takes a long time and should be sped up by considering ### representatives of the orbits under the n-cycle p = (1,...,n). # n := 7;; # p := (1,2,3,4,5,6,7);; # li := Derangements( [1..n] );; # lis := ShallowCopy ( li );; # orbreps := [];; # while lis <> [] do # y := orbitofvector( lis[1], p ) ; Add( orbreps , y[1]); # SubtractSet( lis , y); # od; ### orbreps is now a set of representatives of the orbits of < p > ### on the set of derangements. Since < p > acts on the set of ### normalized r-complete latin squares (by conjugation) it suffices to ### consider elements of orbreps as second rows of the normalized ### latin squares to be tested: # rcomplete7 := [];; # for x in orbreps do # Append( rcomplete7 , latRcomplete( [ [1..n] , x ] , li ) ); # od; # rcomplete7; ## [] ### Example 2 (r-complete latin squares of degree 8) ### # n := 8;; # ma := [ [ 1, 2, 3, 4, 5, 6, 7, 8 ], # [ 2, 1, 4, 3, 6, 5, 8, 7 ] ];; # li := Derangements([1..8]) ;; # res := latRcomplete(ma,li) ;; ## this takes a few hours # Length( res ); ## 16 # List ( res , isLcomplete ) ; ## [ true, true, false, false, false, true, false, true, true, false, true, ## true, true, false, false, false ] # List ( res, x -> IdGroup( groupLQ (x) ) ); ## [ [ 8, 3 ], [ 8, 3 ], [ 128, 928 ], [ 128, 928 ], [ 128, 928 ], [ 8, 3 ], ## [ 128, 928 ], [ 8, 3 ], [ 8, 3 ], [ 128, 928 ], [ 8, 3 ], [ 8, 3 ], ## [ 8, 3 ], [ 128, 928 ], [ 128, 928 ], [ 128, 928 ] ] ## ### So there are 16 extensions of 'ma' to r-complete latin squares of which ### 8 also l-complete. The latter ones are exactly those which are ### based on a group, the dihedral group of order 8 (computed by 'groupLQ'), ### which has GAP-identifier [ 8, 3 ] (returned by IdGroup( ) ), ### the other 8 latin squares all generate (when the rows are considered as ### permutations as above) a group of order 128 with number 928 in the ### library (of groups of order 2^7). In fact the 16 latin squares above ### generate just 2 different groups: # # Set ( List ( res , groupLQ ) ); ## ## [ Group([ (), (1,2)(3,4)(5,6)(7,8), (1,4)(2,7,6,3)(5,8), (1,3,8,6)(2,5,7,4), ## (1,5)(2,6)(3,7)(4,8), (1,7,5,3)(2,8)(4,6), (1,8)(2,3,6,7)(4,5), ## (1,6,8,3,5,2,4,7) ]), ### has Order 128 ## Group([ (), (1,2)(3,4)(5,6)(7,8), (1,3,5,7)(2,8,6,4), (1,6)(2,5)(3,8)(4,7), ## (1,4)(2,7)(3,6)(5,8), (1,8)(2,3)(4,5)(6,7), (1,7,5,3)(2,4,6,8), ## (1,5)(2,6)(3,7)(4,8) ]) ] ### the dihedral group # Display ( res[1] ); ## [ [ 1, 2, 3, 4, 5, 6, 7, 8 ], ## [ 2, 1, 4, 3, 6, 5, 8, 7 ], ## [ 3, 8, 5, 2, 7, 4, 1, 6 ], ## [ 6, 5, 8, 7, 2, 1, 4, 3 ], ## [ 4, 7, 6, 1, 8, 3, 2, 5 ], ## [ 8, 3, 2, 5, 4, 7, 6, 1 ], ## [ 7, 4, 1, 6, 3, 8, 5, 2 ], ## [ 5, 6, 7, 8, 1, 2, 3, 4 ] ] ### ### Example 3 (r-complete latin squares based on D_8) ### ### Instead of continuing with the last example, we start anew (at the same ### point) and want to find all r-complete latin squares based on the ### dihedral group (in its regular representation found in the last example). # G := Group([(1,2)(3,4)(5,6)(7,8), (1,3,5,7)(2,8,6,4)]) ;; # IdGroup(G); ## [ 8, 3 ] # ma := List( Elements(G) , ListPerm);; ma[1] := [1 .. 8];; # Display (ma); ## [ [ 1, 2, 3, 4, 5, 6, 7, 8 ], ## [ 2, 1, 4, 3, 6, 5, 8, 7 ], ## [ 3, 8, 5, 2, 7, 4, 1, 6 ], ## [ 4, 7, 6, 1, 8, 3, 2, 5 ], ## [ 5, 6, 7, 8, 1, 2, 3, 4 ], ## [ 6, 5, 8, 7, 2, 1, 4, 3 ], ## [ 7, 4, 1, 6, 3, 8, 5, 2 ], ## [ 8, 3, 2, 5, 4, 7, 6, 1 ] ] # 1cols := groupbasedlatRcomplete( ma , [1] );; # Length( 1cols ); ## 64 # ForAll( 1cols , x -> isLcomplete( ma{x}) ); ## true ## ### Thus there are 64 normalized r-complete latin squares based on G , ### which you obtain as matrices as { ma{x} | x in 1cols} , or in ### GAP-notation List( 1cols , x -> ma{x} ); . The example ### displayed in the end of Example 2 is ma{ 1cols[1] } . ### All these 64 latin squares are also l-complete. ### ### Example 4 (r-complete latin squares based on C_3 x C_3) ### # der:=Derangements([1..9]);; # li:=Filtered( der , x-> Order( PermList(x)) = 3 );; # Length(li); ## 2240 # p:=(1,2,3,4,5,6,7,8,9);; orbreps := [];; lis :=ShallowCopy(li);; # while lis <> [] do # Add(orbreps, lis[1]); # y := orbitofvector( lis[1], p ) ; SubtractSet( lis , y); # od; # Length(orbreps); ## 256 ### As in Example 1 we calculated a set of representatives 'orbreps' ### of the orbits of

on the set of derangements of order 3, which are ### candidates for the second row x of a latin square based on C_3 x C_3. ### All other rows y must commute (when considered as a permutation) ### with x and in addition y^-1 * x must be a derangement. Using ### these restrictions makes the backtrack search feasible: # res3x3 :=[];; x:=[];; # for x in orbreps do # lis := Filtered( li , y -> PermList(x) * PermList(y) = # PermList(y) * PermList(x) and # ListPerm( PermList(y)^-1 * PermList(x) ) in li ) ; # res:= latRcomplete( [ [1..9] , x ] , lis); # Append( res3x3 , res ); # od; # Length( res3x3 ); ## 0 ### So no r-complete latin squares based on C_3 x C_3 exist . ### ### Example 5 (r-complete latin squares based on C_9) ### # p := (1,2,3,4,5,6,7,8,9) ;; # cl := ConjugacyClassSubgroups( SymmetricGroup(9), Group( p ) ) ;; # cl := AsList(cl) ;; Length(cl); ## 6720 # lc9 := [];; ma:= [];; grouplist := [];; # for x in cl do # ma := List(Elements(x),ListPerm ); ma[1] := [1..9]; # 1cols := groupbasedlatRcomplete( ma , [1] ); # if 1cols <> [] then # Append (lc9 , List ( 1cols , y -> ma{y} ) ); # Add ( grouplist , x); # fi; # od; # Length( lc9 ); ## 648 ### This is the total number of normalized l-complete latin squares of ### order 9 based on a cyclic group. The corresponding groups were ### collected in the list 'grouplist'. # Length( grouplist ); ## 56 # grli := Set( ShallowCopy( grouplist ) );; grouporb := [];; # while grli <> [] do # Add( grouporb, grli[1] ); # orb := Set( List([ 1 .. Order( p )], i-> grli[1]^(p ^ i) )); # SubtractSet( grli, orb); Print( Length(orb),",\c"); # od; ## 9,9,9,9,9,9,1,1, ### 'cl' is the list of all (6720) cyclic subgroups of order 9 of S_9. ### Of these 56 yield r-complete latin squares. Under the action of

### these groups form 6 orbits of length 9 and two of length 1. We ### compute the number of normalized r-complete latin squares these ### groups provide: # for g in grouporb do # ma := List( Elements(g), ListPerm); ma[1] := [1..9]; # Print(Length(groupbasedlatRcomplete( ma , [1] ) ),",\c"); # od; ## 6,6,6,6,6,6,162,162, ### Thus exactly half of the 648 normalized l-complete latin squares ### are based on one of the two groups invariant under p . ### ### Example 6 (r-complete latin squares based on C_n (n = q^2 , q odd) ### # n := 25;; q := 5;; # l := List( [1..n] , i -> RemInt( (q+1) * i + 1 , n) );; # l[ Position(l,0) ] := n;; # g := Elements( Group( PermList(l) ) );; Size(g) ; ## 25 # ma := List( g , ListPerm) ;; ma[1] := [1..n];; # li := [1, 6, 2, 7, 8, 13, 19, 24, 10, 15, 12, 11];; # cols := groupbasedlatLRcomplete( ma , li ); ## [ [ 1, 6, 2, 7, 8, 13, 19, 24, 10, 15, 12, 11, 14, 3, 16, 20, 22, 5, 21, 4, ## 23, 25, 17, 9, 18 ], ## [ 1, 6, 2, 7, 8, 13, 19, 24, 10, 15, 12, 11, 14, 23, 25, 17, 9, 3, 16, 20, ## 22, 5, 21, 4, 18 ], ## [ 1, 6, 2, 7, 8, 13, 19, 24, 10, 15, 12, 11, 18, 16, 20, 4, 17, 9, 23, 25, ## 3, 22, 5, 21, 14 ] ] ### Thus we have found 3 l-r-complete latin squares based on our group ### (with the first 12 rows prescribed by 'li' ). There are a lot more ### squares based on our group which are r-complete but not l-complete. ### ### Example 7 (r-complete latin squares based on C_7.C_3) ### # n := 21;; # a := ( 1, 2,18)( 3,7,8)(4,5,21)(6,10,11)(9,13,14)(12,16,17)(15,19,20);; # b := ( 1, 4, 7,10,13,16,19)(2,8,14,20,5,11,17)(3,15,6,18,9,21,12);; # G := Group( a, b );; # Order(G); ## 21 # IsAbelian(G); ## false # ma := List( Elements(Group(a,b)) , ListPerm );; ma[1] := [1..n];; # res := groupbasedlatLRcomplete( ma , [ 1, 2, 4, 5, 8, 10, 15] ); ## [ [ 1, 2, 4, 5, 8, 10, 15, 16, 9, 11, 6, 21, 3, 18, 14, 17, 12, 19, ## 20, 7, 13 ] ] ### So there is just one l-r-complete latin square based on G with ### the first 7 rows as given. On the other hand, the number of ### such squares which are just r-complete is very large. #################################################################### # Functions : #################################################################### groupLQ := function(ma) # computes the group generated by the rows of 'ma' considered as # permutations of n = Length(ma) return(Group(List(ma , x -> PermList(x) ) )); end; orbitofvector := function ( x, p ) # Input: 'x' = [s(1),...,s(n)] for s in S_n # 'p' in S_n # Output: Orbit { [t(1),...,t(n)] | t = p^{-i}*s*p^i , i = 0,1,... } local res, i; res := [ x ]; for i in [ 1 .. Order( p ) - 1 ] do Add( res, ListPerm( PermList( x ) ^ (p ^ i) ) ); od; return Set( res ); end; orbitLQ := function ( ma, p ) # Input: 'ma' = latin square of size n # 'p' in S_n # Output: Orbit of 'ma' und operation (by conjugation) of

local res, i, max; res := [ ma ]; for i in [ 1 .. Order( p ) - 1 ] do max := List([1..Length(ma[1])], j -> ListPerm(PermList( ma[j])^(p^i)) ); max[1] := [1..Length(ma[1])]; Add( res, max ); od; return Set( res ); end; isRcomplete := function( ma ) # The mxn-matrix 'ma' (with entries in [1..n]) is tested for r-completeness local n, m, i, j, lis, ex, done; m := Length( ma ); n := Length( ma[1] ); ex := [ ]; done := false; j := 0; while done = false do j := j + 1; if j = n then done := true; fi; lis := List( [ 1 .. m - 1 ], i -> ma[i + 1][RemInt( Position( ma[i], j ), n ) + 1] ); if m = n then Add( lis, ma[1][RemInt( Position( ma[m], j ), n ) + 1] ); if Length( Set( lis ) ) < m then done := true; else Add( ex, 1 ); fi; else if Length( Set( lis ) ) < m - 1 then done := true; else Add( ex, 1 ); fi; fi; od; if Length( ex ) = n then return true; else return false; fi; return; end; isLcomplete := function( ma ) # The mxn-matrix 'ma' is tested for l-completeness local n, m, i, j, lis, ex, done; m := Length( ma ); n := Length( ma[1] ); ex := [ ]; done := false; j := 0; while done = false do j := j + 1; if j = n then done := true; fi; lis := List( [ 1 .. m - 1 ], i -> ma[i + 1][RemInt( Position( ma[i], j ) + n - 2, n ) + 1] ); if m = n then Add( lis, ma[1][RemInt( Position( ma[m], j ) + n - 2, n ) + 1] ); if Length( Set( lis ) ) < m then done := true; else Add( ex, 1 ); fi; else if Length( Set( lis ) ) < m - 1 then done := true; else Add( ex, 1 ); fi; fi; od; if Length( ex ) = n then return true; else return false; fi; return; end; latext := function( ma, li ) # for a latin mxn-rectangle 'ma' and a list 'li' of permutations # of n (as row-vectors) those permutations of 'li' are filtered out # and returned as output # which can be added to 'ma' in order to obtain a latin (m+1)xn rectangle local i, x, y, res, n; res := [ ]; n := Length( ma[1] ); for y in li do if ForAll( ma, x -> ForAll( [ 1 .. n ], i -> y[i] <> x[i] ) ) then Add( res, y ); fi; od; return res; end; latRext := function( ma, li ) # for an r-complete latin mxn-rectangle 'ma' and a list 'li' of permutations # of n (as row-vectors) those permutations of 'li' are filtered out # and returned as output # which can be added to 'ma' in order to obtain an r-complete latin # (m+1)xn rectangle local i, x, lmat, res, m, n; m := Length( ma ); n := Length( ma[1] ); res := [ ]; lmat:=List( [1..n] , i -> List( [1..m-1], j -> ma[j+1][RemInt(Position(ma[j],i),n)+1])); for x in li do if ForAll([1..n], i-> not x[RemInt(Position(ma[m],i),n)+1] in lmat[i] ) then Add(res,x); fi; od; return res; end; latLRext := function( ma, li ) # for a l- r-complete latin mxn-rectangle 'ma' and a list 'li' of permutations # of n (as row-vectors) those permutations of 'li' are filtered out # and returned as output # which can be added to 'ma' in order to obtain a l-r-complete latin # (m+1)xn rectangle local i, der, x, y, mat, res, m, n; m := Length( ma ); n := Length( ma[1] ); res := [ ]; der := ShallowCopy( li ); for x in ma do der := Filtered( der, y -> ForAll( [ 1 .. n ], i -> y[i] <> x[i] ) ); od; for x in der do mat := ShallowCopy( ma ); Add( mat, x ); if isRcomplete( mat ) and isLcomplete( mat ) then Add( res, x ); fi; od; return res; end; latRcomplete := function( ma, li ) # for a latin mxn rectangle 'ma' and a list 'li' of permutations # of n (as row-vectors) all r-complete latin squares are # constructed with the first m rows being those of 'ma' and the # remaining ones taken from 'li' # the program uses a backtrack-search and will finish only in # reasonable time, if n - m is not too large. local i, res, n, x, y, z, done, zp; n := Length( ma[1] ); x := ShallowCopy( ma ); y := [ ]; res := [ ]; zp := [ ]; done := false; zp[1] := latext( x, li ); i := 1; y[1] := latRext( x, zp[1] ); while done = false do i := i + 1; if y[i - 1] <> [ ] then Add( x, y[i - 1][1] ); if Length( x ) = n then if isRcomplete( x ) then Add( res, x ); # Print( "\n", x ); ## fi; Unbind( y[i - 1][1] ); y[i - 1] := Set( y[i - 1] ); x := x{[ 1 .. Length( x ) - 1 ]}; i := i - 1; else zp[i] := latext( x, zp[i - 1] ); z := latRext( x, zp[i] ); if z <> [ ] then y[i] := z; else x := x{[ 1 .. Length( x ) - 1 ]}; Unbind( y[i - 1][1] ); y[i - 1] := Set( y[i - 1] ); i := i - 1; fi; fi; else if i = 2 then done := true; else Unbind( y[i - 2][1] ); y[i - 2] := Set( y[i - 2] ); Unbind( zp[i] ); x := x{[ 1 .. Length( x ) - 1 ]}; i := i - 2; fi; fi; if i < 1 then done := true; fi; od; return res; end; latLRcomplete := function( ma, li ) # for a latin mxn rectangle 'ma' and a list 'li' of permutations # of n (as row-vectors) all l-r-complete latin squares are # constructed with the first m rows being those of 'ma' and the # remaining ones taken from 'li' # the program uses a backtrack-search and will finish only in # reasonable time, if n - m is not too large. local i, res, n, x, y, z, done, zp; n := Length( ma[1] ); x := ShallowCopy( ma ); y := [ ]; res := [ ]; zp := [ ]; done := false; zp[1] := latext( x, li ); i := 1; y[1] := latLRext( x, zp[1] ); while done = false do i := i + 1; if y[i - 1] <> [ ] then Add( x, y[i - 1][1] ); if Length( x ) = n then if isRcomplete( x ) and isLcomplete( x ) then Add( res, x ); # Print( "\n", x ); ## fi; Unbind( y[i - 1][1] ); y[i - 1] := Set( y[i - 1] ); x := x{[ 1 .. Length( x ) - 1 ]}; i := i - 1; else zp[i] := latext( x, zp[i - 1] ); z := latLRext( x, zp[i] ); if z <> [ ] then y[i] := z; else x := x{[ 1 .. Length( x ) - 1 ]}; Unbind( y[i - 1][1] ); y[i - 1] := Set( y[i - 1] ); i := i - 1; fi; fi; else if i = 2 then done := true; else Unbind( y[i - 2][1] ); y[i - 2] := Set( y[i - 2] ); Unbind( zp[i] ); x := x{[ 1 .. Length( x ) - 1 ]}; i := i - 2; fi; fi; if i < 1 then done := true; fi; od; return res; end; groupbasedlatRext := function( ma, li ) # Input: 'ma' =[a_{i,j}] a latin nxn-square based on a group # in standard form, i.e. with a_{i,1} = i , # li = [i_1,...,i_m] a subsequence of [1..n] such that # ma{li} is an r-complete latin mxn-rectangle. # Output: List of all j such that row ma[j] added to ma{li} # yields an r-complete latin (m+1)xn-rectangle. local i, diff, mat, res, m, n; if not isRcomplete( ma{li} ) then Print( "ERROR ", li, "\n" ); else n := Length( ma ); m := Length( li ); res := [ ]; diff := Difference( [ 1 .. n ], li ); for i in diff do mat := ShallowCopy( ma{li} ); Add( mat, ma[i] ); if isRcomplete( mat ) then Add( res, i ); fi; od; return res; fi; return; end; groupbasedlatLRext := function( ma, li ) # Input: 'ma' =[a_{i,j}] a latin nxn-square based on a group (see Def in # section 2) in standard form, i.e. with a_{i,1} = i , # li = [a_1,...,a_m] a subsequence of [1..n] such that # ma{li} is an lr-complete latin mxn-rectangle. # Output: List of all j such that row ma[j] added to ma{li} # yields an lr-complete latin (m+1)xn-rectangle. local i, diff, mat, res, m, n; if not isRcomplete( ma{li} ) and not isLcomplete( ma{li} ) then Print( "ERROR ", li, "\n" ); else n := Length( ma ); m := Length( li ); res := [ ]; diff := Difference( [ 1 .. n ], li ); for i in diff do mat := ShallowCopy( ma{li} ); Add( mat, ma[i] ); if isRcomplete( mat ) and isLcomplete( mat ) then Add( res, i ); fi; od; return res; fi; return; end; groupbasedlatRcomplete := function( ma, li ) # Input: 'ma' =[a_{i,j}] a latin nxn-square based on a group (see Def in # section 2) in standard form, i.e. with a_{i,1} = i , # li = [a_1,...,a_m] a subsequence of [1..n] such that # ma{li} is an r-complete latin mxn-rectangle. # Output: List of all j such that row ma[j] added to ma{li} # yields an r-complete latin (m+1)xn-rectangle. local i, res, m, n, x, y, z, done; m := Length( li ); n := Length( ma ); res := [ ]; x := ShallowCopy( li ); y := [ ]; done := false; i := 1; y[1] := groupbasedlatRext( ma, li ); while done = false do i := i + 1; if y[i - 1] <> [ ] then Add( x, y[i - 1][1] ); if Length( x ) = n then if isRcomplete( ma{x} ) then Add( res, x ); fi; Unbind( y[i - 1][1] ); y[i - 1] := Set( y[i - 1] ); x := x{[ 1 .. Length( x ) - 1 ]}; i := i - 1; else z := groupbasedlatRext( ma, x ); if z <> [ ] then y[i] := z; else x := x{[ 1 .. Length( x ) - 1 ]}; Unbind( y[i - 1][1] ); y[i - 1] := Set( y[i - 1] ); i := i - 1; fi; fi; else if i = 2 then done := true; else Unbind( y[i - 2][1] ); y[i - 2] := Set( y[i - 2] ); x := x{[ 1 .. Length( x ) - 1 ]}; i := i - 2; fi; fi; if i < 1 then done := true; fi; od; return res; end; groupbasedlatLRcomplete := function( ma, li ) # Input: 'ma' =[a_{i,j}] a latin nxn-square based on a group (see Def in # section 2) in standard form, i.e. with a_{i,1} = i , # li = [a_1,...,a_m] a subsequence of [1..n] such that # ma{li} is an lr-complete latin mxn-rectangle. # Output: List of all j such that row ma[j] added to ma{li} # yields an lr-complete latin (m+1)xn-rectangle. local i, res, m, n, x, y, z, done; m := Length( li ); n := Length( ma ); res := [ ]; x := ShallowCopy( li ); y := [ ]; done := false; i := 1; y[1] := groupbasedlatLRext( ma, li ); while done = false do i := i + 1; if y[i - 1] <> [ ] then Add( x, y[i - 1][1] ); if Length( x ) = n then if isRcomplete( ma{x} ) and isLcomplete( ma{x} ) then Add( res, x ); # Print("\n",x); ######## fi; Unbind( y[i - 1][1] ); y[i - 1] := Set( y[i - 1] ); x := x{[ 1 .. Length( x ) - 1 ]}; i := i - 1; else z := groupbasedlatLRext( ma, x ); if z <> [ ] then y[i] := z; else x := x{[ 1 .. Length( x ) - 1 ]}; Unbind( y[i - 1][1] ); y[i - 1] := Set( y[i - 1] ); i := i - 1; fi; fi; else if i = 2 then done := true; else Unbind( y[i - 2][1] ); y[i - 2] := Set( y[i - 2] ); x := x{[ 1 .. Length( x ) - 1 ]}; i := i - 2; fi; fi; if i < 1 then done := true; fi; od; return res; end;