""" Random latin square generator using the Method of Circuts. Model implementation in Python using simple search for symbol conflicts. Larry Trammell -- May 2020 This supports the document "Direct Construction of Random Latin Squares by the Method of Circuits" and is publicly distributed under the Creative Commons CC-BY-4.0 license. """ # Define row-column dimensions of square to be constructed Nrc = 10 # Python system imports import random as rnpy # core random number generator import numpy as np # compact numeric data types from copy import deepcopy # data replicator for initialization """ Conflict resolution operations """ # Find a column term that conflicts with a newly inserted term. # If found, return the row index for the conflicting symbol. If not # found, return artificial flag value -1. def findConflictInCol(A, iviol, jviol, sym1) : Nrc=len(A) irow = -1 for itest in range(Nrc) : if itest == iviol : continue if A[itest,jviol] == 0 : continue if A[itest,jviol] == sym1 : irow = itest break return irow # Find a row term that conflicts with a newly inserted term. # If found, return the column index for the conflicting symbol. # if not, return the artificial flag value -1. def findConflictInRow(A, iviol, jviol, sym2) : Nrc=len(A) jcol = -1 for jtest in range(Nrc) : if jtest == jviol : continue if A[iviol,jtest] == 0 : continue if A[iviol,jtest] == sym2 : jcol = jtest break return jcol """ Main generator sequence """ print("Generating a Latin Square of size ", Nrc,"x",Nrc) # Initialize an empty square A = np.zeros((Nrc,Nrc), dtype=np.short) # Initialize feasible symbols sets for rows and cols row = [ ] for j in range(Nrc) : row.append( np.short(j+1) ) rowavail = [ ] for i in range(Nrc) : rowavail.append( set(row) ) colavail = deepcopy(rowavail) # Assigning symbols to layout cells in row-column lexical order. for i in range(Nrc) : for j in range(Nrc): # Check for row-column feasible symbols at this new location avail = rowavail[i] & colavail[j] if len(avail) > 0 : # FEASIBLE. Assign a randomly-selected feasible symbol. sel=rnpy.sample(avail,1) symbol1 = sel[0] A[i,j] = symbol1 rowavail[i].remove(symbol1) colavail[j].remove(symbol1) else : # CONFLICT. Insert a randomly-selected row-feasible SYMBOL1 sel=rnpy.sample(rowavail[i],1) symbol1 = sel[0] A[i,j] = symbol1 rowavail[i].remove(symbol1) # Randomly select a column-feasible replacement SYMBOL2 sel=rnpy.sample(colavail[j],1) symbol2 = sel[0] # Begin conflict resolution at the newly-assigned cell. iviol = i jviol = j while(True) : # Locate row of the violating symbol in column jviol iviol = findConflictInCol(A, iviol, jviol, symbol1) if iviol == -1 : # If no conflict, resolution is complete break # Remove SYMBOL1 from this circuit location rowavail[iviol].add(symbol1) # Replace with SYMBOL2 A[iviol,jviol] = symbol2 colavail[jviol].remove(symbol2) if symbol2 in rowavail[iviol] : rowavail[iviol].remove(symbol2) # Locate column of the violating symbol in row iviol jviol = findConflictInRow(A, iviol, jviol, symbol2) if jviol == -1 : # If no conflict, resolution is complete break # Remove SYMBOL2 from this circuit location colavail[jviol].add(symbol2) # Replace with SYMBOL1 A[iviol,jviol] = symbol1 rowavail[iviol].remove(symbol1) if symbol1 in colavail[jviol] : colavail[jviol].remove(symbol1) pass pass pass print("\nCompleted square ") print(A) #print("\nVerify row and column sums") #rowsum = [0]*Nrc #colsum = [0]*Nrc #for i in range(Nrc) : # for j in range(Nrc) : # rowsum[i] = rowsum[i]+A[i,j] # colsum[j] = colsum[j]+A[i,j] #print("rowsum :", rowsum) #print("colsum :", colsum)