How Convenient Graeco-Latin Squares AreFrom schedule creation to cryptographic mechanismsJuan Manuel DatoBlockedUnblockFollowFollowingMay 18In combinatorics, a Graeco-Latin square or Euler square or pair of orthogonal Latin squares of order n over two sets S and T, each consisting of n symbols, is an n×narrangement of cells, each cell containing an ordered pair (s,t), where s is in S and t is in T, such that every row and every column contains each element of S and each element of T exactly once, and that no two cells contain the same ordered pairImagine a sample of four batches of people having to try four products in four different environments, if we only want to spend four stages, how should they be organized?The products are A, B, C,…, and the environment α , β, γ,… First stage: Aα , Bγ, …Or also, imagine four athletes coming together to compete in five sports against each other and against the clock; after holding the 25 competitions, how do you do it so that it is done in five phases?In a championship with an irregular public there is a league between 13 teams (an odd number) with only 7 tracks (less than 13), how to allocate the tracks so that the league is held in a manner spread over the least number of seasons?How should the students of an academy be classified among 5 tutors so that they acquire five competencies promised in up to 5 rooms in a distribution of 5 or more teachers?Acquiring the skills necessary to understand how Graeco-Latin squares work simplifies scheduling problems.
Generating some easy samplesThe first thing before generating a graeco-latin square is to begin with a latin square.
Latin Square of order 3As you can see, if you sum the ord of the coordinates row and column in modulo the order, you can find easily one.
So, can we reach one in the same way for a graeco-latin square?To get the same opperation we need a spetial column that is a permutation of (0 1 2 3 … n), with n the order of the graeco-latin square.
But that permutation needs to be a swap like you can see in the next figure:Three possible cases where arrows generate cyclesUnderstanding we only need to generate a cycle we can guess what will happen if we calculate a tuple (…, 6, 4, 2, 0, -2, -4, -6, …), in modulo 2n+1 the negative will be converted in the odd numbers we need.
So:def genGL(n, inString = False): if n % 2 == 0: return R = [-2*(i+1) for i in range(n//2)] R = [n+1+X for X in R]+[0]+R if inString: return [[repr((X+Y)%n)+'/'+repr((X+Y+R[X])%n) for Y in range(n)] for X in range(n)] else: return [[((X+Y)%n, (X+Y+R[X])%n) for Y in range(n)] for X in range(n)]With this code you can generate any graeco-latin square of odd order, as you can test with this other code:>>> from numpy import matrix>>> matrix(genGL(7, True))matrix([['0/6', '1/0', '2/1', '3/2', '4/3', '5/4', '6/5'], ['1/5', '2/6', '3/0', '4/1', '5/2', '6/3', '0/4'], ['2/4', '3/5', '4/6', '5/0', '6/1', '0/2', '1/3'], ['3/3', '4/4', '5/5', '6/6', '0/0', '1/1', '2/2'], ['4/2', '5/3', '6/4', '0/5', '1/6', '2/0', '3/1'], ['5/1', '6/2', '0/3', '1/4', '2/5', '3/6', '4/0'], ['6/0', '0/1', '1/2', '2/3', '3/4', '4/5', '5/6']], dtype='<U3')>>> genGL(3)[[(0, 2), (1, 0), (2, 1)], [(1, 1), (2, 2), (0, 0)], [(2, 0), (0, 1), (1, 2)]]It is possible to create any graeco-latin square of order different to 6, but odd orders are easier to code.
A symmetric codeA symmetric code consists of encrypting the information in such a way that, applying the same key that encrypted it, the information can be recovered as it was.
A simple example can be seen in this code that swaps a list of items.
def decodeMerge (N): 'Generates a pair of positions to be exchanged' A=ceil((-1+sqrt(1+8*(N+1)))/2) B=N-A*(A-1)//2 return (A,B)def merge(L, P = 0): 'Mix the list L according to swap P' N=len(L) def swap(pos1, pos2): X = L[pos1 % N] L[pos1 % N] = L[pos2 % N] L[pos2 % N] = X toBin = [P for P, X in enumerate(bin(abs(P))[2:]) if X == '1'] if P>=0: toBin.
reverse() for X in toBin: swap(*decodeMerge(X))You can understand how it works with the next code: You have a list L=['pawn', 'horse', 'bishop', 'rook', 'queen', 'king'] That’s your original message, and your passwordwill any great number, for example you can type password = 246.
Then, you can try this:>>> (L, password)(['pawn', 'horse', 'bishop', 'rook', 'queen', 'king'], 246)>>> merge(L, password)>>> L['bishop', 'rook', 'horse', 'queen', 'pawn', 'king']>>> merge(L, -password)>>> L['pawn', 'horse', 'bishop', 'rook', 'queen', 'king']A problem with this code is that you need to remember very big passwords, but if you combine this with your knowledge of graeco-latin squares you will find different ways to generate symmetrical encryptions.
.