|
%I #9 Feb 08 2020 13:31:11
%S 3,8,3,8,3,8
%N a(n) is the minimum number of transversals in Latin squares of order n that have at least 1 transversal.
%C We find all the transversals of the main class representatives of order n Latin squares then find the one with the fewest transversals.
%H Brendan McKay, <a href="https://users.cecs.anu.edu.au/~bdm/data/latin.html">Latin squares</a>
%e For n = 5,they are 2 main classes of Latin squares. One of them has representative M = [[1,2,3,4,5],[2,4,1,5,3],[3,5,4,2,1],[4,1,5,3,2],[5,3,2,1,4]], and it has 3 transversals; {M(1,1), M(5,2), M(3,3), M(2,4), M(4,5)}, {M(2,1), M(5,2), M(4,3), M(1,4), M(3,5)}, and {M(4,1), M(5,2), M(2,3), M(3,4), M(1,5)}. The other main class representative [[1,2,3,4,5],[2,3,4,5,1],[3,4,5,1,2],[4,5,1,2,3],[5,1,2,3,4]] has 15 transversals. Therefore, the minimum number of transversals in order 5 Latin squares is 3, i.e., a(5) = 3.
%o (MATLAB)
%o %This extracts entries from each column. For an example, if
%o %A=[1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16], and if list = (2, 1, 4),
%o %this code extracts the second element in the first column, the first
%o %element in the second column, and the fourth element in the third column.
%o function [output] = extract(matrix,list)
%o for i=1:length(list)
%o output(i) = matrix(list(i),i);
%o end
%o end
%o %Searches matrix to find transversal and outputs the transversal.
%o function [output] = findtransversal(matrix)
%o n=length(matrix);
%o for i=1:n
%o partialtransversal(i,1)=i;
%o end
%o for i=2:n
%o newpartialtransversal=[];
%o for j=1:length(partialtransversal)
%o for k=1:n
%o if (~ismember(k,partialtransversal(j,:)))&(~ismember(matrix(k,i),extract(matrix,partialtransversal(j,:))))
%o newpartialtransversal=[newpartialtransversal;[partialtransversal(j,:),k]];
%o end
%o end
%o end
%o partialtransversal=newpartialtransversal;
%o end
%o output=partialtransversal;
%o end
%o %Takes input of n^2 numbers with no spaces between them and converts it
%o %into an n by n matrix.
%o function [A] = tomatrix(input)
%o n=sqrt(floor(log10(input))+2);
%o for i=1:n^2
%o temp(i)=mod(floor(input/(10^(i-1))),10);
%o end
%o for i=1:n
%o for j=1:n
%o A(i,j)=temp(n^2+1-(n*(i-1)+j));
%o end
%o end
%o A=A+ones(n);
%o end
%K nonn,hard,more
%O 3,1
%A _Alvaro R. Belmonte_, _Eugene Fiorini_, _Peterson Lenard_, _Froylan Maldonado_, _Sabrina Traver_, _Wing Hong Tony Wong_, Jul 24 2019
|
