Navigation
In this post, I will avoid much of the preliminary information needed to understand and work with Latin squares. The focus of the post is to provide details about a Latin square class written in C++ built with the application developer in mind. That is, the intent of this C++ class is to allow someone who is working with Latin squares a way to interact with the objects without actually building and maintaining their own implementation. The post will provide information to that end but will avoid much of the description, application, and general information about Latin squares.
Overview
A Latin square is a combinatorial object described as a square array that contains n different elements with each element occurring n times but with no element occurring twice in the same column or row. I was introduced to these objects as an undergraduate when I decided to study combinatorics for my undergraduate thesis. My university didn’t offer a course in combinatorics so this was the only way for me to get exposure to the field. The complete thesis write-up can be found on my GitHub, bear in mind that I wrote this report quite a while ago and consider myself a better writer now (if I could go back 5 years…)
My major professor decided that Latin squares would be our object of study and for the next 2 years, my time was consumed by generating Matlab code to work with these square arrays: generating them, determining their properties, and uncovering facts that were already well-known in the field.
This Matlab logic worked well for small order Latin squares (up to about order 5) but for higher-order squares, the processing took too long. (Some of this could possibly be attributed to my skill with Matlab at the time, but likely not all of it.) After trying to increase performance with some other languages I determined the best choice was probably going to be C++. My initial stab at Latin square processing with C++ wasn’t great, but it did the job. Some of this old source code can be found on my GitHub repository.
When writing the C++ classes I knew that I would need to keep high-performance computing applications in mind since the number of Latin squares of each order increases combinatorially. Therefore, when creating the class I was focused on being able to easily translate the logic for use in MPI, Pthreads, and Cuda applications as well as efficiently working with the square data. Due to the focus on Cuda applications, I decided to work with 1-D C++ arrays to store the square data. Code running on Cuda devices cannot (easily) use 2-D arrays, it’s much simpler to pass around the vector (flattened) form of the array.
My Latin square research interests pertain to mutually orthogonal Latin squares. Thus, much of the functionality currently implemented in the class handles generating squares of a certain order, checking for orthogonality, and checking certain other properties of the square.
Implementation
As mentioned above this Latin square class was created with generating squares and checking for orthogonality in mind. There are two versions on my GitHub: a header-only version and one with the class definition and implementation in separate header and C++ files, respectively. The split implementation is usually kept up to date since this is the one I use in my applications. Some of the functionality isn’t explicitly lain out below, but full source code is given at the end of this article and is available in my repository.
Below is the header file for this version,
#include <string>
#include <cstring> // memset
#include <iostream>
#include <fstream>
#include "InvalidSquareException.h"
using namespace std;
class LatinSquare
{
public:
LatinSquare(short order); // kind of useless constructor
LatinSquare(short order, short* values);
LatinSquare(short order, short* values, short iso_class);
LatinSquare(short order, short* values, short iso_class, short main_class);
LatinSquare(const LatinSquare& ls); // copy constructor
// change the square
void set_iso_class(short iso_class) { this->iso_class = iso_class; };
void set_main_class(short main_class) { this->main_class = main_class; };
void set_values(short* sq_values);
void permute_rows(short* new_rows);
void permute_cols(short* new_cols);
void permute_symbols(short* syms);
void rcs_permutation(short* rcs);
void normalize();
// square properties
bool is_symmetric();
bool is_orthogonal(LatinSquare sq);
bool is_normal();
bool is_valid();
// visualization
string tostring();
void print();
friend ostream& operator<<(ostream& os, const LatinSquare sq);
void output_values_space(ofstream& os);
void print_flat();
string flatstring();
string flatstring_no_space();
short* get_values() {return values;}
// operators
bool operator==(const LatinSquare &chk_sq) const;
bool operator!=(const LatinSquare &chk_sq) const;
private:
short order = -1; // technically = i due to o_sq = -1
short* values = NULL;
short iso_class = -1;
short o_sq = -1;
short main_class = -1;
void move_row(short curr_row, short new_row, short *new_values);
void move_col(short curr_col, short new_col, short *new_values);
InvalidSquareException invalidExcept;
};
As seen above, the class offers functionality to view and print the squares, set the square properties (main class, isotopy class, symmetric, etc.), to determine orthogonality, and to generate more Latin squares. All Latin squares of a certain order can be generated provided a list of a few squares known as isotopy class representatives. These representatives have their rows, columns, and symbols moved around (permuted) to generate new squares. Selecting the distinct squares from all newly generated squares provides every square of that order. Likewise, there is an equivalence in Latin squares known as main class equivalence. The main classes are created by interchanging rows, columns, and symbols, i.e. a square’s row values could become its symbol values (more information can be found in my undergraduate report). This class is set up to handle both types of equivalency.
Constructors
Below are the constructors used to instantiate this class. Keep in mind that, for some reason, although I was using C++ 11 constructor delegation was ruining the reference to the squares data values so much of the code is repeated.
// delegated constructors not working with gcc/g++, even after specifying c++11 and checking g++ version
LatinSquare::LatinSquare(short order)
{
this->order = order;
this->o_sq = order * order;
}
LatinSquare::LatinSquare(short order, short* values)
{
this->order = order;
this->o_sq = order * order;
this->values = values;
if (values != NULL)
{
set_values(values); // if initialized with actual values, verify they are valid
}
}
LatinSquare::LatinSquare(short order, short* values, short iso_class)
{
this->order = order;
this->o_sq = order * order;
this->values = values;
if (values != NULL)
{
set_values(values); // if initialized with actual values, verify they are valid
}
this->iso_class = iso_class;
}
LatinSquare::LatinSquare(short order, short* values, short iso_class, short main_class)
{
this->order = order;
this->o_sq = order * order;
this->values = values;
if (values != NULL)
{
set_values(values); // if initialized with actual values, verify they are valid
}
this->iso_class = iso_class;
this->main_class = main_class;
}
LatinSquare::LatinSquare(const LatinSquare& cls)
{
order = cls.order;
o_sq = cls.o_sq;
values = NULL;
if (cls.values != NULL)
{
// deep copy the array
values = new short[o_sq];
memcpy(values, cls.values, sizeof(short) * o_sq);
}
iso_class = -1;
main_class = -1;
}
These constructors are pretty straightforward in how they set certain values of the square.
Isotopy Class Operations
As mentioned above, two squares can be isotopic or have isotopy equivalency if one can be generated by permuting the rows, columns, and symbols of the other. Below is my implementation of the functionality needed to perform these operations.
Permute Rows
void LatinSquare::permute_rows(short* new_rows)
{
if (!is_valid())
{
throw invalidExcept;
return;
}
short* new_values = new short[o_sq];
for (short i = 0; i < order; i++)
{
move_row(i, new_rows[i], new_values);
}
delete[] values;
set_values(new_values);
}
/**
* Sets the values in the new array at row (new_row) to the values in the current
* array at row (curr_row).
**/
void LatinSquare::move_row(short curr_row, short new_row, short* new_values)
{
for (short i = 0; i < order; i++)
{
new_values[curr_row * order + i] = values[new_row * order + i];
}
}
Permute Columns
void LatinSquare::permute_cols(short *new_cols)
{
if(!is_valid())
{
throw invalidExcept;
return;
}
short *new_values = new short[o_sq];
for(short i = 0; i < order; i++)
{
move_col(i, new_cols[i], new_values);
}
delete[] values;
set_values(new_values);
}
void LatinSquare::move_col(short curr_col, short new_col, short *new_values)
{
for (short i = 0; i < order; i++)
{
new_values[i * order + curr_col] = values[i * order + new_col];
}
}
Permute Symbols
void LatinSquare::permute_symbols(short* syms)
{
// index syms based on current square values to get updated values
short* new_vals = new short[o_sq];
for (short i = 0; i < o_sq; i++)
{
new_vals[i] = syms[values[i]];
}
delete[] values;
set_values(new_vals);
}
Shown above is the logic to move around the rows, columns, and symbols of a Latin square. Performing each of these operations for every possible permutation of n values, where n is the squares’ order, will create every square of that order. These operations have to be applied to every isotopy class representative and each generated square until no new squares are created. I will discuss this more in a future blog post.
Main Class Equivalence
Similar to isotopy class equivalence, main class equivalence operates on representative squares to create every square in a main class. Performing these operations on a representative for each main class will generate every square of any order. The operation consists of swapping the values that represent the rows, columns, and symbols of a square with one another. There are 6=3! possible permutations of row, column, and symbol values to be applied to each square (and each generated square). Below is the logic that handles this interchanging operation.
void LatinSquare::rcs_permutation(short* rcs)
{
// should be able to grab the current (R, C, S) triple and
// index those values based on the current rcs permutation (param).
// If the symbol becomes the row, then rcs[0] will be 2. This 2 will
// index triple[2] which gives the row to be used in the new_value
// index calculation.
short j = -1;
short trip[3];
short* new_vals = new short[o_sq];
for (short i = 0; i < o_sq; i++)
{
if (i % order == 0)
j++;
trip[1] = i % order; // row
trip[0] = j; // col
trip[2] = values[(j * order) + (i % order)]; // curr value
new_vals[(trip[rcs[0]] * order) + trip[rcs[1]]] = trip[rcs[2]];
}
delete[] values;
set_values(new_vals);
}
Checking for Orthogonality
Since most of my work is focused on orthogonal Latin squares, the Latin square class implements a function to determine if two squares are orthogonal to one another.
bool LatinSquare::is_orthogonal(LatinSquare chk_sq)
{
if (!is_valid() || !chk_sq.is_valid())
{
throw invalidExcept;
return false;
}
if (order != chk_sq.order) // must be the same size
return false;
// mark off the pairs in this table, if the table is marked the pair has been used
// and the squares are not orthogonal.
bool** pairs = new bool*[order];
for (short i = 0; i < order; i++)
pairs[i] = new bool[order];
for (short i = 0; i < order; i++)
{
for (short j = 0; j < order; j++)
{
pairs[i][j] = false;
}
}
for (short i = 0; i < o_sq; i++)
{
short idx1 = values[i] % order;
short idx2 = chk_sq.values[i] % order;
if (pairs[idx1][idx2])
{
delete[] pairs;
return false;
}
else
{
pairs[idx1][idx2] = true;
}
}
delete[] pairs;
return true;
}
This function works by creating an n x n array of boolean values that act as a lookup table. Every time a pair, say (2, 2), is pulled from the two Latin squares that we are checking for orthogonality, the array’s row 2 column 2 value is checked. If the value in, for example, index (2,2) is marked true the squares are not orthogonal since (2, 2) has appeared before. If the value is marked false the value is updated to true and processing continues.
Other Functionality
The Latin square class offers a slew of other functionality but most of it is either self-explanatory or not worth mentioning in this post. For example, there are a few different methods that print the square in different ways for different purposes,
// visualization string tostring(); void print(); friend ostream& operator<<(ostream& os, const LatinSquare sq); void output_values_space(ofstream& os); void print_flat(); string flatstring(); string flatstring_no_space();
other functionality to determine equality,
bool operator==(const LatinSquare &chk_sq) const; bool operator!=(const LatinSquare &chk_sq) const;
and some other miscellaneous methods for house-keeping, ease-of-use, or property storage,
bool is_symmetric();
bool is_normal();
bool is_valid();
void set_iso_class(short iso_class) { this->iso_class = iso_class; };
void set_main_class(short main_class) { this->main_class = main_class; };
void set_values(short* sq_values);
void normalize();
short* get_values() {return values;}
This functionality is either straightforward or otherwise not worth expounding on in this article.
Full Source Code
Below is the full source code for the class header, class implementation, and header-only Latin square class. These classes and other logic pertaining to my Latin squares research can be found, as mentioned, in my GitHub repository. Note that some functionality may be missing from the header-only implementation. I try to keep them updated but use the separated implementation more frequently.
LatinSquare.h
#include <string>
#include <cstring> // memset
#include <iostream>
#include <fstream>
#include "InvalidSquareException.h"
using namespace std;
class LatinSquare
{
public:
LatinSquare(short order); // kind of useless constructor
LatinSquare(short order, short* values);
LatinSquare(short order, short* values, short iso_class);
LatinSquare(short order, short* values, short iso_class, short main_class);
LatinSquare(const LatinSquare& ls); // copy constructor
// change the square
void set_iso_class(short iso_class) { this->iso_class = iso_class; };
void set_main_class(short main_class) { this->main_class = main_class; };
void set_values(short* sq_values);
void permute_rows(short* new_rows);
void permute_cols(short* new_cols);
void permute_symbols(short* syms);
void rcs_permutation(short* rcs);
void normalize();
// square properties
bool is_symmetric();
bool is_orthogonal(LatinSquare sq);
bool is_normal();
bool is_valid();
// visualization
string tostring();
void print();
friend ostream& operator<<(ostream& os, const LatinSquare sq);
void output_values_space(ofstream& os);
void print_flat();
string flatstring();
string flatstring_no_space();
short* get_values() {return values;}
// operators
bool operator==(const LatinSquare &chk_sq) const;
bool operator!=(const LatinSquare &chk_sq) const;
// implemented so we std::set can be use which requires unique data be stored
// this makes creating the collection of all squares MUCH faster
bool operator<(const LatinSquare &chk_sq) const;
private:
short order = -1; // technically = i due to o_sq = -1
short* values = NULL;
short iso_class = -1;
short o_sq = -1;
short main_class = -1;
void move_row(short curr_row, short new_row, short *new_values);
void move_col(short curr_col, short new_col, short *new_values);
InvalidSquareException invalidExcept;
};
LatinSquare.cpp
#include "LatinSquare.h"
// delegated constructors not working with gcc/g++, even after specifying c++11
LatinSquare::LatinSquare(short order)
{
this->order = order;
this->o_sq = order * order;
}
LatinSquare::LatinSquare(short order, short* values)
{
this->order = order;
this->o_sq = order * order;
this->values = values;
if (values != NULL)
{
set_values(values); // if initialized with actual values, verify they are valid
}
}
LatinSquare::LatinSquare(short order, short* values, short iso_class)
{
this->order = order;
this->o_sq = order * order;
this->values = values;
if (values != NULL)
{
set_values(values); // if initialized with actual values, verify they are valid
}
this->iso_class = iso_class;
}
LatinSquare::LatinSquare(short order, short* values, short iso_class, short main_class)
{
this->order = order;
this->o_sq = order * order;
this->values = values;
if (values != NULL)
{
set_values(values); // if initialized with actual values, verify they are valid
}
this->iso_class = iso_class;
this->main_class = main_class;
}
LatinSquare::LatinSquare(const LatinSquare& cls)
{
order = cls.order;
o_sq = cls.o_sq;
values = NULL;
if (cls.values != NULL)
{
// deep copy the array
values = new short[o_sq];
memcpy(values, cls.values, sizeof(short) * o_sq);
}
iso_class = -1;
main_class = -1;
}
string LatinSquare::tostring()
{
string lsstr = "";
if (values != NULL)
{
for (int i = 0; i < o_sq; i++)
{
if (i % order == 0 && i > 0)
lsstr += "\n";
lsstr += to_string(values[i]) + " ";
}
}
else
{
lsstr = "An empty Latin square of order " + to_string(order) + ".\n";
}
return lsstr;
}
string LatinSquare::flatstring()
{
string flatstr = "";
if(values != NULL)
{
for(short i = 0; i < o_sq; i++)
{
flatstr += to_string(values[i]) + " ";
}
}
else
{
flatstr = "An empty Latin square of order " + to_string(order);
}
return flatstr + "\n";
}
string LatinSquare::flatstring_no_space()
{
string flatstr = "";
if(values != NULL)
{
for(short i = 0; i < o_sq; i++)
{
flatstr += to_string(values[i]);
}
}
else
{
flatstr = "An empty Latin square of order " + to_string(order);
}
return flatstr;
}
void LatinSquare::print()
{
cout << tostring() << endl;
}
void LatinSquare::print_flat()
{
if(values != NULL)
{
for(short i = 0; i < o_sq; i++)
{
cout << values[i];
}
}
cout << endl;
}
void LatinSquare::output_values_space(ofstream &os)
{
for (short i = 0; i < o_sq; i++)
os << values[i] << " ";
os << endl;
}
ostream& operator<<(ostream& os, const LatinSquare sq)
{
if (sq.values != NULL)
{
for (int i = 0; i < sq.o_sq; i++)
{
if (i % sq.order == 0 && i > 0)
os << "\n";
os << to_string(sq.values[i]) + " ";
}
}
else
{
os << to_string(sq.order);
}
return os;
}
bool LatinSquare::is_symmetric()
{
if (!is_valid())
{
throw invalidExcept;
return false;
}
// probably doens't work
short* rows = new short[o_sq];
short* cols = new short[o_sq];
short j = -1; // start at -1 to prevent i>0 check everytime in the loop
for (short i = 0; i < o_sq; i++)
{
if (i % order == 0)
j++;
rows[i] = values[i];
cols[i] = values[((i*order) % o_sq) + j]; // hardest math here
}
for (short i = 0; i < o_sq; i++)
{
if (rows[i] != cols[i]) // if they ever differ, not symmetric
{
delete[] rows;
delete[] cols;
return false;
}
}
delete[] rows;
delete[] cols;
return true;
}
bool LatinSquare::is_normal()
{
short* rows = new short[order];
short* cols = new short[order];
for (short i = 0; i < order; i++)
{
cols[i] = values[i];
rows[i] = values[(i*order)]; // hardest math here
}
for (short i = 0; i < order; i++)
{
if (rows[i] != i || cols[i] != i) // if they ever differ, not symmetric
{
delete[] rows;
delete[] cols;
return false;
}
}
return true;
}
bool LatinSquare::is_orthogonal(LatinSquare chk_sq)
{
if (!is_valid() || !chk_sq.is_valid())
{
throw invalidExcept;
return false;
}
if (order != chk_sq.order) // must be the same size
return false;
// mark off the pairs in this table, if the table is marked the pair has been used
// and the squares are not orthogonal.
bool** pairs = new bool*[order];
for (short i = 0; i < order; i++)
pairs[i] = new bool[order];
for (short i = 0; i < order; i++)
{
for (short j = 0; j < order; j++)
{
pairs[i][j] = false;
}
}
for (short i = 0; i < o_sq; i++)
{
short idx1 = values[i] % order;
short idx2 = chk_sq.values[i] % order;
if (pairs[idx1][idx2])
{
delete[] pairs;
return false;
}
else
{
pairs[idx1][idx2] = true;
}
}
delete[] pairs;
return true;
}
bool LatinSquare::is_valid()
{
if (values == NULL)
{
return false;
}
// mark the row/col check matrices, each index should be marked once for each
// row and column for the square to be valid.
bool* row_chk = new bool[order];
bool* col_chk = new bool[order];
short j = -1;
for (short i = 0; i < o_sq; i++)
{
// the check arrays should be filled every time we do 'order' number of checks
// need to reset them to all false
if (i % order == 0)
{
memset(row_chk, 0, order * sizeof(bool));
memset(col_chk, 0, order * sizeof(bool));
j++;
}
short row_idx = values[i] % order;
short col_idx = values[((i * order) % o_sq) + j] % order;
if (col_chk[col_idx] || row_chk[row_idx]) // same number twice (already marked)
{
delete[] row_chk;
delete[] col_chk;
return false;
}
else
{
col_chk[col_idx] = true;
row_chk[row_idx] = true;
}
}
delete[] row_chk;
delete[] col_chk;
return true;
}
void LatinSquare::set_values(short* sq_values)
{
this->values = sq_values;
if (!is_valid())
{
cout << "WARNING: Invalid values for latin square..." << endl;
//this->print();
}
}
void LatinSquare::permute_rows(short* new_rows)
{
if (!is_valid())
{
throw invalidExcept;
return;
}
short* new_values = new short[o_sq];
for (short i = 0; i < order; i++)
{
move_row(i, new_rows[i], new_values);
}
delete[] values;
set_values(new_values);
}
void LatinSquare::permute_cols(short *new_cols)
{
if(!is_valid())
{
throw invalidExcept;
return;
}
short *new_values = new short[o_sq];
for(short i = 0; i < order; i++)
{
move_col(i, new_cols[i], new_values);
}
delete[] values;
set_values(new_values);
}
void LatinSquare::rcs_permutation(short* rcs)
{
// should be able to grab the current (R, C, S) triple and
// index those values based on the current rcs permutation (param).
// If the symbol becomes the row, then rcs[0] will be 2. This 2 will
// index triple[2] which gives the row to be used in the new_value
// index calculation.
short j = -1;
short trip[3];
short* new_vals = new short[o_sq];
for (short i = 0; i < o_sq; i++)
{
if (i % order == 0)
j++;
trip[1] = i % order; // row
trip[0] = j; // col
trip[2] = values[(j * order) + (i % order)]; // curr value
new_vals[(trip[rcs[0]] * order) + trip[rcs[1]]] = trip[rcs[2]];
}
delete[] values;
set_values(new_vals);
}
void LatinSquare::normalize()
{
short* perm = new short[order];
for(int i = 0; i < order; i++)
{
perm[values[i]] = i;
}
permute_cols(perm);
for(int i = 0; i < order; i++)
{
perm[values[i*order]] = i;
}
permute_rows(perm);
}
void LatinSquare::permute_symbols(short* syms)
{
// index syms based on current square values to get updated values
short* new_vals = new short[o_sq];
for (short i = 0; i < o_sq; i++)
{
new_vals[i] = syms[values[i]];
}
delete[] values;
set_values(new_vals);
}
/**
* Sets the values in the new array at row (new_row) to the values in the current
* array at row (curr_row).
**/
void LatinSquare::move_row(short curr_row, short new_row, short* new_values)
{
for (short i = 0; i < order; i++)
{
new_values[curr_row * order + i] = values[new_row * order + i];
}
}
void LatinSquare::move_col(short curr_col, short new_col, short *new_values)
{
for (short i = 0; i < order; i++)
{
new_values[i * order + curr_col] = values[i * order + new_col];
}
}
bool LatinSquare::operator==(const LatinSquare &chk_sq) const
{
if (values == NULL || chk_sq.values == NULL) // are empty, invalid squares not equal? should we compare the sizes?
{
throw invalidExcept;
return false;
}
if (chk_sq.order != order) // same order?
return false;
for (short i = 0; i < o_sq; i++) // same values?
if (values[i] != chk_sq.values[i])
return false;
return true;
}
bool LatinSquare::operator!=(const LatinSquare &chk_sq) const
{
return !(*this == chk_sq);
}
bool LatinSquare::operator<(const LatinSquare &chk_sq) const
{
// use the string representation of the squares to determine if two squares
// are equal (essentially). A LS being less than another LS doesn't really
// make sense so this is my way around that to use std::set objects in dealing
// with squares.
string thisStr = "";
if(values != NULL)
{
for(short i = 0; i < o_sq; i++)
{
thisStr += to_string(values[i]);
}
}
else
{
thisStr = "An empty Latin square of order " + to_string(order);
}
string checkStr = "";
if(values != NULL)
{
for(short i = 0; i < o_sq; i++)
{
checkStr += to_string(chk_sq.values[i]);
}
}
else
{
checkStr = "An empty Latin square of order " + to_string(order);
}
return thisStr < checkStr;
}
LatinSquare_hdrOnly.hpp (Header-only Implementation)
#include <string>
#include <cstring> // memset
#include <iostream>
#include <fstream>
using namespace std;
class InvalidSquareException : public exception
{
virtual const char* what() const throw()
{
return "Attempting to operate on invalid square.";
}
};
class LatinSquare
{
public:
LatinSquare(short order); // kind of useless constructor
LatinSquare(short order, short* values);
LatinSquare(short order, short* values, short iso_class);
LatinSquare(short order, short* values, short iso_class, short main_class);
LatinSquare(const LatinSquare& ls); // copy constructor
// change the square
void set_iso_class(short iso_class) { this->iso_class = iso_class; };
void set_main_class(short main_class) { this->main_class = main_class; };
void set_values(short* sq_values);
void permute_rows(short* new_rows);
void permute_cols(short* new_cols);
void permute_symbols(short* syms);
void rcs_permutation(short* rcs);
// square properties
bool is_symmetric();
bool is_orthogonal(LatinSquare sq);
bool is_valid();
// visualization
string tostring();
void print();
friend ostream& operator<<(ostream& os, const LatinSquare sq);
void output_values_space(ofstream& os);
void print_flat();
string flatstring();
short* get_values() {return values;}
// operators
const bool operator==(const LatinSquare &chk_sq) const;
const bool operator!=(const LatinSquare &chk_sq) const;
private:
short order = -1; // technically = i due to o_sq = -1
short* values = NULL;
short iso_class = -1;
short o_sq = -1;
short main_class = -1;
void move_row(short curr_row, short new_row, short *new_values);
void move_col(short curr_col, short new_col, short *new_values);
InvalidSquareException invalidExcept;
};
// delegated constructors not working with gcc/g++, even after specifying c++11
LatinSquare::LatinSquare(short order)
{
this->order = order;
this->o_sq = order * order;
}
LatinSquare::LatinSquare(short order, short* values)
{
this->order = order;
this->o_sq = order * order;
this->values = values;
if (values != NULL)
{
set_values(values); // if initialized with actual values, verify they are valid
}
}
LatinSquare::LatinSquare(short order, short* values, short iso_class)
{
this->order = order;
this->o_sq = order * order;
this->values = values;
cout << this->values << endl;
if (values != NULL)
{
set_values(values); // if initialized with actual values, verify they are valid
}
this->iso_class = iso_class;
}
LatinSquare::LatinSquare(short order, short* values, short iso_class, short main_class)
{
this->order = order;
this->o_sq = order * order;
this->values = values;
cout << this->values << endl;
if (values != NULL)
{
set_values(values); // if initialized with actual values, verify they are valid
}
this->iso_class = iso_class;
this->main_class = main_class;
}
LatinSquare::LatinSquare(const LatinSquare& cls)
{
order = cls.order;
o_sq = cls.o_sq;
values = NULL;
if (cls.values != NULL)
{
// deep copy the array
values = new short[o_sq];
memcpy(values, cls.values, sizeof(short) * o_sq);
}
iso_class = -1;
main_class = -1;
}
string LatinSquare::tostring()
{
string lsstr = "";
if (values != NULL)
{
for (int i = 0; i < o_sq; i++)
{
if (i % order == 0 && i > 0)
lsstr += "\n";
lsstr += to_string(values[i]) + " ";
}
}
else
{
lsstr = "An empty Latin square of order " + to_string(order) + ".\n";
}
return lsstr;
}
string LatinSquare::flatstring()
{
string flatstr = "";
if(values != NULL)
{
for(short i = 0; i < o_sq; i++)
{
flatstr += to_string(values[i]) + " ";
}
}
else
{
flatstr = "An empty Latin square of order " + to_string(order);
}
return flatstr + "\n";
}
void LatinSquare::print()
{
cout << tostring() << endl;
}
void LatinSquare::print_flat()
{
if(values != NULL)
{
for(short i = 0; i < o_sq; i++)
{
cout << values[i];
}
}
cout << endl;
}
void LatinSquare::output_values_space(ofstream &os)
{
for (short i = 0; i < o_sq; i++)
os << values[i] << " ";
os << endl;
}
ostream& operator<<(ostream& os, const LatinSquare sq)
{
if (sq.values != NULL)
{
for (int i = 0; i < sq.o_sq; i++)
{
if (i % sq.order == 0 && i > 0)
os << "\n";
os << to_string(sq.values[i]) + " ";
}
}
else
{
os << to_string(sq.order);
}
return os;
}
bool LatinSquare::is_symmetric()
{
if (!is_valid())
{
throw invalidExcept;
return false;
}
short* rows = new short[o_sq];
short* cols = new short[o_sq];
short j = -1; // start at -1 to prevent i>0 check everytime in the loop
for (short i = 0; i < o_sq; i++)
{
if (i % order == 0)
j++;
rows[i] = values[i];
cols[i] = values[((i*order) % o_sq) + j]; // hardest math here
}
for (short i = 0; i < o_sq; i++)
{
if (rows[i] != cols[i]) // if they ever differ, not symmetric
{
delete[] rows;
delete[] cols;
return false;
}
}
delete[] rows;
delete[] cols;
return true;
}
bool LatinSquare::is_orthogonal(LatinSquare chk_sq)
{
if (!is_valid() || !chk_sq.is_valid())
{
throw invalidExcept;
return false;
}
if (order != chk_sq.order) // must be the same size
return false;
// mark off the pairs in this table, if the table is marked the pair has been used
// and the squares are not orthogonal.
bool** pairs = new bool*[order];
for (short i = 0; i < order; i++)
pairs[i] = new bool[order];
for (short i = 0; i < order; i++)
{
for (short j = 0; j < order; j++)
{
pairs[i][j] = false;
}
}
for (short i = 0; i < o_sq; i++)
{
short idx1 = values[i] % order;
short idx2 = chk_sq.values[i] % order;
if (pairs[idx1][idx2])
{
delete[] pairs;
return false;
}
else
{
pairs[idx1][idx2] = true;
}
}
delete[] pairs;
return true;
}
bool LatinSquare::is_valid()
{
if (values == NULL)
{
return false;
}
// mark the row/col check matrices, each index should be marked once for each
// row and column for the square to be valid.
bool* row_chk = new bool[order];
bool* col_chk = new bool[order];
short j = -1;
for (short i = 0; i < o_sq; i++)
{
// the check arrays should be filled every time we do 'order' number of checks
// need to reset them to all false
if (i % order == 0)
{
memset(row_chk, 0, order * sizeof(bool));
memset(col_chk, 0, order * sizeof(bool));
j++;
}
short row_idx = values[i] % order;
short col_idx = values[((i * order) % o_sq) + j] % order;
if (col_chk[col_idx] || row_chk[row_idx]) // same number twice (already marked)
{
delete[] row_chk;
delete[] col_chk;
return false;
}
else
{
col_chk[col_idx] = true;
row_chk[row_idx] = true;
}
}
delete[] row_chk;
delete[] col_chk;
return true;
}
void LatinSquare::set_values(short* sq_values)
{
this->values = sq_values;
if (!is_valid())
{
cout << "WARNING: Invalid values for latin square..." << endl;
this->print();
}
}
void LatinSquare::permute_rows(short* new_rows)
{
if (!is_valid())
{
throw invalidExcept;
return;
}
short* new_values = new short[o_sq];
for (short i = 0; i < order; i++)
{
move_row(i, new_rows[i], new_values);
}
delete[] values;
set_values(new_values);
}
void LatinSquare::permute_cols(short *new_cols)
{
if(!is_valid())
{
throw invalidExcept;
return;
}
short *new_values = new short[o_sq];
for(short i = 0; i < order; i++)
{
move_col(i, new_cols[i], new_values);
}
delete[] values;
set_values(new_values);
}
void LatinSquare::rcs_permutation(short* rcs)
{
// should be able to grab the current (R, C, S) triple and
// index those values based on the current rcs permutation (param).
// If the symbol becomes the row, then rcs[0] will be 2. This 2 will
// index triple[2] which gives the row to be used in the new_value
// index calculation.
short j = -1;
short trip[3];
short* new_vals = new short[o_sq];
for (short i = 0; i < o_sq; i++)
{
if (i % order == 0)
j++;
trip[1] = i % order; // row
trip[0] = j; // col
trip[2] = values[(j * order) + (i % order)]; // curr value
new_vals[(trip[rcs[0]] * order) + trip[rcs[1]]] = trip[rcs[2]];
}
delete[] values;
set_values(new_vals);
}
void LatinSquare::permute_symbols(short* syms)
{
// index syms based on current square values to get updated values
short* new_vals = new short[o_sq];
for (short i = 0; i < o_sq; i++)
{
new_vals[i] = syms[values[i]];
}
delete[] values;
set_values(new_vals);
}
/**
* Sets the values in the new array at row (new_row) to the values in the current
* array at row (curr_row).
**/
void LatinSquare::move_row(short curr_row, short new_row, short* new_values)
{
for (short i = 0; i < order; i++)
{
new_values[new_row * order + i] = values[curr_row * order + i];
}
}
void LatinSquare::move_col(short curr_col, short new_col, short *new_values)
{
for (short i = 0; i < order; i++)
{
new_values[i * order + curr_col] = values[i * order + new_col];
}
}
const bool LatinSquare::operator==(const LatinSquare &chk_sq) const
{
if (values == NULL || chk_sq.values == NULL) // are empty, invalid squares not equal? should we compare the sizes?
{
throw invalidExcept;
return false;
}
if (chk_sq.order != order) // same order?
return false;
for (short i = 0; i < o_sq; i++) // same values?
if (values[i] != chk_sq.values[i])
return false;
return true;
}
const bool LatinSquare::operator!=(const LatinSquare &chk_sq) const
{
return !(*this == chk_sq);
}