""" This module implements the prefill variant of the "Method of Circuits" using additional reverse-lookup indexing arrays so that a symbol can be located in any row or column in a single operation. This improves efficiency, but costs 2*N^2 additional storage locations and additional per-location overhead. Usage: # Construct generator using default configuration options import rlatin5MOCi rg = rlatin5MOCi.rlatin( 64 ) # Build the Latin Square rg.randomize() # Access the result ls = rg.store This code is provided Sept. 10, 2023 by its author Larry Trammell under the CC0 license; see https://creativecommons.org/publicdomain/zero/1.0/ """ # Python system imports import numpy as np # numeric data types from copy import deepcopy # data replicator for initialization # Random variate generation import numpy.random as rn # random selection functions import random as rnpy # core random number generator from numpy.random import Generator, PCG64, MT19937 rg = Generator( PCG64() ) #rg = Generator(MT19937()) ### =================================================================== # Local randomizing functions # Pick an integer randomly and uniformly in the range of 0 to Nrc-1 def randix( NN ) : rv = rg.choice(NN, shuffle=False) return rv ### =================================================================== # Latin Square generator class for the Method of Circuits generator # using O(1) indexing arrays instead of direct line searches. # The class includes a 2-D area for storing the constructed Latin # Square object, and also reserves the selection and indexing arrays. # class rlatin : 'Defines a base class for a randomized Latin square in a 2-D array' # The constructor method reserves storage and size information. # def __init__(self, Nrc, Nprobes=0) : # Size configuration parameter preserved self.Nrc = int(Nrc) self.Nprobes = Nprobes # Various "flag" constants for content and state self.empty = np.short(-1) self.filled = np.short(1) self.unfilled = np.short(0) # Reserve storage for layout content self.store = 0 # Reserve storage for row and column availability sets self.rowavail = 0 self.colavail = 0 # Reserve storage for lookup indexing tables self.rowx = 0 self.colx = 0 # Reserve a pool of array locations for random selection self.poolset = 0 # Reserve statistics for computational effort monitoring self.Conflicts = 0 self.Steps = 0 # Establish initial state, including storage and indexing arrays allocations self.clear( ) # Row / column line search methods. Because the O(1) indexing arrays # are available, these simply wrap the array accesses as methods. Returns # the index if symbol is found; or returns special value 'empty' when # symbol is not present. # def findinrow( self, row, sym) : found = self.colx[row,sym] return found def findincol( self, col, sym) : found = self.rowx[col,sym] return found # Utility to clear the internal storage areas for a clean restart. # def clear(self) : # Storage, pre-allocated but without meaningful content self.store = np.zeros((self.Nrc,self.Nrc), dtype=np.short) for row in range(self.Nrc) : for col in range(self.Nrc) : self.store[row,col] = self.empty # Reset the row and column availability sets to "all symbols" # for every row and every column self.rowavail = [ { } ]*self.Nrc self.colavail = [ { } ]*self.Nrc for term in range(self.Nrc) : self.rowavail[term] = set( range(self.Nrc) ) self.colavail[term] = set( range(self.Nrc) ) # Row-column indexing starts with no symbols assigned. self.rowx = np.ndarray((self.Nrc,self.Nrc), dtype=np.short) self.colx = np.ndarray((self.Nrc,self.Nrc), dtype=np.short) for term in range(self.Nrc) : for sym in range(self.Nrc) : self.rowx[term,sym] = self.empty self.colx[term,sym] = self.empty # Generate a shuffled pool of all row-column locations Nrc2 = self.Nrc * self.Nrc self.poolset = [ (self.empty, self.empty) ]*Nrc2 for row in range(self.Nrc) : for col in range(self.Nrc) : ix = row * self.Nrc + col self.poolset[ix] = (np.short(row),np.short(col)) rg.shuffle( self.poolset) # Clear internal statistics self.Conflicts = 0 self.Steps = 0 # -------------------------------------------------------------------- # # The initial pre-fill pass, inserting symbol content as much as # possible without violating Latin constraints. # # Starting with clear storage, make one attempt to assign every cell # a feasible symbol, chosen randomly from row and column availability. # If there is a conflict at any cell, return its row-col index # pair to the pool and continue, leaving the cell unassigned -- a # CONFLICT. # def pass1_preassign(self) : # There will be N**2 attempts to fill cells, once per each cell # in the randomized selection pool. for selx in range(self.Nrc * self.Nrc) : # From shuffled pool, take the first cell pair rc = self.poolset.pop(0) row = rc[0] col = rc[1] # If there is no feasible symbol assignment, leave this cell empty # and return the conflicted cell location to the selection pool. avail = self.rowavail[row] & self.colavail[col] if len(avail) == 0 : # Return the unused cell-pair to end of the pool list self.store[row,col] = self.empty self.poolset.append(rc) self.Conflicts += 1 continue # Otherwise, a feasible assignment exists. Pick one randomly. # Add cell to symbol indexing arrays and remove from availability. sel=rnpy.sample(avail,1) sym = sel[0] self.store[row,col] = sym self.rowx[col,sym] = row self.colx[row,sym] = col self.rowavail[row].remove(sym) self.colavail[col].remove(sym) self.Steps += 1 # -------------------------------------------------------------------- # # Resolution pass, to complete a symbol assignment for the Latin Square. # # Utility to empty the contents of a specified row and column location. # Return the prior symbol assignment from that cell if any. Update indexing. # def clear_cell( self, row, col ) : # If cell happens to be already empty, nothing to do sym = self.store[row,col] if self.store[row,col] == self.empty : return self.empty # Clear the cell and symbol indexing self.store[row,col] = self.empty self.rowx[col, sym] = self.empty self.colx[row, sym] = self.empty # Restore removed symbol to availability lists self.rowavail[row].add(sym) self.colavail[col].add(sym) return sym # Utility to inject new contents into an empty cell at the the # specified row and column location. Update indexing. def inject_cell( self, row, col, sym ) : # Store assigned symbol in cell self.store[row,col] = sym # Update the cell and symbol indexing self.rowx[col, sym] = row self.colx[row, sym] = col # Remove symbol from row and col availability lists self.rowavail[row].remove(sym) self.colavail[col].remove(sym) # Cycle through the conflicted cells, as listed in the index pairs # remaining in the cell selection pool. Find a symbol that can fill # each of these cells, applying a circuit trace with symbol swapping # whenever symbol insertion produces a new conflict. def pass2_resolve(self) : # Continue while any cell without an assigned label remains while len(self.poolset) != 0 : # Take the next empty row-column location from the pool list rc = self.poolset.pop(0) row1 = rc[0] col1 = rc[1] # Resolve immediately if a symbol is available for both row and column. avail = self.rowavail[row1] & self.colavail[col1] if len(avail) > 0 : sym1 = avail.pop() self.inject_cell(row1,col1,sym1) self.Steps = self.Steps + 1 continue # the main loop # Otherwise, select a row available symbol and column available symbol # for the circuit trace. sym1 = self.rowavail[row1].pop() self.rowavail[row1].add(sym1) sym2 = self.colavail[col1].pop() self.colavail[col1].add(sym2) # Begin tracing a circuit with symbol replacement. Continue the # trace until no symbol conflict exists. # Invariant: values of sym1 and sym2 do not change # Invariant: at the beginning of each pass, cell at row1, col1 # is unassigned while (True) : # Check whether injecting sym1 at the empty cell causes a conflict row2 = self.rowx[col1,sym1] if row2 == self.empty : # Add symbo1 to empty cell and trace is done self.inject_cell(row1,col1,sym1) self.Steps = self.Steps + 1 break # Clear sym1 from the conflicting cell before filling empty cell self.clear_cell(row2,col1) self.inject_cell(row1,col1,sym1) self.Steps = self.Steps + 1 # Check whether injecting sym2 into the new row will cause a row conflict col2 = self.colx[row2,sym2] if col2 == self.empty : # Add symbo1 to empty cell and trace is done self.inject_cell(row2,col1,sym2) self.Steps = self.Steps + 1 break # Clear sym2 from the conflicting cell before filling empty cell self.clear_cell(row2,col2) self.inject_cell(row2,col1,sym2) self.Steps = self.Steps + 1 # Prepare to trace the next pair of transitions along the circuit row1 = row2 col1 = col2 # End of inner loop # End of the outer loop return # End of resolve method # -------------------------------------------------------------------- # # Pass 3 bias corrections. # # Utility to locate a circuit of maximal length in a completed Latin Square. # Give up and return 'None' if the testing fails to find one withing the # specified limit on the number of probes. Otherwise, report the two symbols # and the start location. # def FindAMaxCirc( self, Nprobes ) : for test in range(Nprobes) : # Select a start row-column position randomly x1 = randix( self.Nrc ) y1 = randix( self.Nrc ) # Select another row position in column for the second symbol x2 = randix( self.Nrc - 1) if x2==x1 : x2 = self.Nrc - 1 # Identify symbols from storage sym1 = self.store[x1,y1] sym2 = self.store[x2,y1] # Begin tracing a circuit here, looking for symbol pair rowcount = 0 xs = x1 ys = y1 while True : # Advance along column to symbol sym2 x1 = self.rowx[y1,sym2] # Advance along row to symbol sym1 y1 = self.colx[x1,sym1] rowcount = rowcount+1 if x1 == xs : break # Did we find maximal? if rowcount == self.Nrc : return (xs, ys, sym1, sym2) # Circuit was not maximal. Try again with another pair. # All probes failed. return None # End of FindAMaxCirc search method # Utility to select a "split location" randomly along the circuit specified by # a start location and symbol pair. Return the row and column indices of this # second location. # def FindEndLoc( self, x1, y1, sym1, sym2 ) : # Select a number of steps in range 1 to Nrc-2 randomly steps = randix(self.Nrc - 2) + 1 # Follow circuit this many steps to find the split location. for step in range(steps) : x1 = self.rowx(y1,sym2) y1 = self.colx(x1,sym1) # Return the location of the end cell return (x1, y1) # Perform a splay operation between the corner points along the # circuit at the start location x1,y1 and the end location x2,y2 that both # contain sym1 symbols, thus splitting the circuit into two smaller ones. # def pass3_splay( self ) : # Locate a starting point in a bounded number of search probes startat = self.FindAMaxCirc( self.Nprobes ) if startat == None : # Omit splay operation return None (x1, y1, sym1, sym2) = startat # Locate a break point with sym1. It must exist! (x2, y2) = self.FindEndLoc( x1, y1, sym1, sym2 ) # Find the original row location of sym2 in col y2 x3 = self.rowx[y2,sym2] # Find the original col location of sym2 in row x1 y3 = self.colx[x1,sym2] # Identify the symbols sym3 and sym4 sym3 = self.store[x1,y2] sym4 = self.store[x3,y3] # Clear conflicted cell locations. self.clear_cell( x1,y2 ) self.clear_cell( x3,y2 ) self.clear_cell( x3,y3 ) self.clear_cell( x1,y3 ) # We have an easy special case if sym3 and sym4 happen to match. if sym3 == sym4 : # No traversal is needed. # Restore transposed contents of the conflicted cells. self.inject_cell( x1,y2, sym2 ) self.inject_cell( x3,y3, sym2 ) self.inject_cell( x3,y2, sym3 ) self.inject_cell( x1,y3, sym3 ) return # End of first case # Trace circuit for the case when sym3 and sym4 are different. else : # Prepare for the circuit trace operation. self.inject_cell( x1, y2, sym2 ) self.inject_cell( x3, y3, sym2 ) xcur = x1 ycur = y3 # Trace the circuit, toggling values sym3 and sym4 while True: # Trace along row looking for sym4 conflict ynext = self.colx[xcur,sym4] if ynext == self.empty : self.inject_cell( xcur,ycur, sym4 ) self.inject_cell( x3, y2, sym3) break self.clear_cell( xcur,ynext ) self.inject_cell( xcur,ycur, sym4 ) ycur = ynext # Trace along column looking for sym3 conflict xnext = self.rowx[ycur,sym3] if xnext == self.empty : self.inject_cell( xcur,ycur, sym3 ) self.inject_cell( x3, y2, sym4) break self.clear_cell( xnext, ycur ) self.inject_cell( xcur,ycur, sym3 ) xcur = xnext # End of trace loop # End of second case # End of splay method # -------------------------------------------------------------------- # # Configurable implementation. This is the "generic way" to use the # class. Call this method to generate the randomized Latin Square # content. If the content is already present, this method reinitializes # and replaces the content. # def randomize(self) : # Establish initial cleared state self.clear( ) # Perform feasible assignment pre-fill self.pass1_preassign( ) # Complete a Latin symbol assignment self.pass2_resolve( ) # Perform a bias correction if self.Nprobes > 0 : self.pass3_splay( ) # End of Method of Circuits class