How to resolve the algorithm Latin Squares in reduced form step by step in the Java programming language
How to resolve the algorithm Latin Squares in reduced form step by step in the Java programming language
Table of Contents
Problem Statement
A Latin Square is in its reduced form if the first row and first column contain items in their natural order. The order n is the number of items. For any given n there is a set of reduced Latin Squares whose size increases rapidly with n. g is a number which identifies a unique element within the set of reduced Latin Squares of order n. The objective of this task is to construct the set of all Latin Squares of a given order and to provide a means which given suitable values for g any element within the set may be obtained. For a reduced Latin Square the first row is always 1 to n. The second row is all Permutations/Derangements of 1 to n starting with 2. The third row is all Permutations/Derangements of 1 to n starting with 3 which do not clash (do not have the same item in any column) with row 2. The fourth row is all Permutations/Derangements of 1 to n starting with 4 which do not clash with rows 2 or 3. Likewise continuing to the nth row. Demonstrate by:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Latin Squares in reduced form step by step in the Java programming language
The program computes the number of reduced Latin squares of a given order (n). A Latin square of order (n) is an (n \times n) array filled with (n) different symbols, each occurring exactly once in each row and each column. A reduced Latin square is a Latin square in which the first row and the first column are in natural order. The program works by generating all the reduced Latin squares of a given order and then counting them.
The main function prints the reduced Latin squares of order (4) and then computes the number of Latin squares of order (n) from the count of reduced Latin squares. This is done by multiplying the count of reduced Latin squares by (n! \times (n-1)!).
The getReducedLatinSquares function generates all the reduced Latin squares of a given order (n).
It uses a recursive algorithm that starts with a reduced Latin square of order (1) and then adds one row at a time.
For each row, it generates all the permutations of the symbols that can be placed in that row and checks if each permutation is valid (i.e., it does not conflict with the symbols already placed in the square).
If a permutation is valid, it is added to the list of reduced Latin squares.
The fact function computes the factorial of a number.
It is used to compute the total number of Latin squares of order (n).
The display function is used to print the reduced Latin squares.
The LatinSquare class represents a Latin square.
It has a constructor that takes the order of the square as an argument and initializes the square to the identity matrix.
It also has methods to get and set the value of a cell in the square.
The PermutationGenerator class generates permutations of a given set of symbols.
It has a constructor that takes the number of symbols as an argument and initializes the generator to the identity permutation.
It also has methods to get the next permutation and to check if there are more permutations.
The hasMore method returns true if there are more permutations to generate.
The getNext method returns the next permutation.
The reset method resets the generator to the identity permutation.
Source code in the java programming language
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class LatinSquaresInReducedForm {
public static void main(String[] args) {
System.out.printf("Reduced latin squares of order 4:%n");
for ( LatinSquare square : getReducedLatinSquares(4) ) {
System.out.printf("%s%n", square);
}
System.out.printf("Compute the number of latin squares from count of reduced latin squares:%n(Reduced Latin Square Count) * n! * (n-1)! = Latin Square Count%n");
for ( int n = 1 ; n <= 6 ; n++ ) {
List<LatinSquare> list = getReducedLatinSquares(n);
System.out.printf("Size = %d, %d * %d * %d = %,d%n", n, list.size(), fact(n), fact(n-1), list.size()*fact(n)*fact(n-1));
}
}
private static long fact(int n) {
if ( n == 0 ) {
return 1;
}
int prod = 1;
for ( int i = 1 ; i <= n ; i++ ) {
prod *= i;
}
return prod;
}
private static List<LatinSquare> getReducedLatinSquares(int n) {
List<LatinSquare> squares = new ArrayList<>();
squares.add(new LatinSquare(n));
PermutationGenerator permGen = new PermutationGenerator(n);
for ( int fillRow = 1 ; fillRow < n ; fillRow++ ) {
List<LatinSquare> squaresNext = new ArrayList<>();
for ( LatinSquare square : squares ) {
while ( permGen.hasMore() ) {
int[] perm = permGen.getNext();
// If not the correct row - next permutation.
if ( (perm[0]+1) != (fillRow+1) ) {
continue;
}
// Check permutation against current square.
boolean permOk = true;
done:
for ( int row = 0 ; row < fillRow ; row++ ) {
for ( int col = 0 ; col < n ; col++ ) {
if ( square.get(row, col) == (perm[col]+1) ) {
permOk = false;
break done;
}
}
}
if ( permOk ) {
LatinSquare newSquare = new LatinSquare(square);
for ( int col = 0 ; col < n ; col++ ) {
newSquare.set(fillRow, col, perm[col]+1);
}
squaresNext.add(newSquare);
}
}
permGen.reset();
}
squares = squaresNext;
}
return squares;
}
@SuppressWarnings("unused")
private static int[] display(int[] in) {
int [] out = new int[in.length];
for ( int i = 0 ; i < in.length ; i++ ) {
out[i] = in[i] + 1;
}
return out;
}
private static class LatinSquare {
int[][] square;
int size;
public LatinSquare(int n) {
square = new int[n][n];
size = n;
for ( int col = 0 ; col < n ; col++ ) {
set(0, col, col + 1);
}
}
public LatinSquare(LatinSquare ls) {
int n = ls.size;
square = new int[n][n];
size = n;
for ( int row = 0 ; row < n ; row++ ) {
for ( int col = 0 ; col < n ; col++ ) {
set(row, col, ls.get(row, col));
}
}
}
public void set(int row, int col, int value) {
square[row][col] = value;
}
public int get(int row, int col) {
return square[row][col];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for ( int row = 0 ; row < size ; row++ ) {
sb.append(Arrays.toString(square[row]));
sb.append("\n");
}
return sb.toString();
}
}
private static class PermutationGenerator {
private int[] a;
private BigInteger numLeft;
private BigInteger total;
public PermutationGenerator (int n) {
if (n < 1) {
throw new IllegalArgumentException ("Min 1");
}
a = new int[n];
total = getFactorial(n);
reset();
}
private void reset () {
for ( int i = 0 ; i < a.length ; i++ ) {
a[i] = i;
}
numLeft = new BigInteger(total.toString());
}
public boolean hasMore() {
return numLeft.compareTo(BigInteger.ZERO) == 1;
}
private static BigInteger getFactorial (int n) {
BigInteger fact = BigInteger.ONE;
for ( int i = n ; i > 1 ; i-- ) {
fact = fact.multiply(new BigInteger(Integer.toString(i)));
}
return fact;
}
/*--------------------------------------------------------
* Generate next permutation (algorithm from Rosen p. 284)
*--------------------------------------------------------
*/
public int[] getNext() {
if ( numLeft.equals(total) ) {
numLeft = numLeft.subtract (BigInteger.ONE);
return a;
}
// Find largest index j with a[j] < a[j+1]
int j = a.length - 2;
while ( a[j] > a[j+1] ) {
j--;
}
// Find index k such that a[k] is smallest integer greater than a[j] to the right of a[j]
int k = a.length - 1;
while ( a[j] > a[k] ) {
k--;
}
// Interchange a[j] and a[k]
int temp = a[k];
a[k] = a[j];
a[j] = temp;
// Put tail end of permutation after jth position in increasing order
int r = a.length - 1;
int s = j + 1;
while (r > s) {
int temp2 = a[s];
a[s] = a[r];
a[r] = temp2;
r--;
s++;
}
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
}
}
You may also check:How to resolve the algorithm Loops/Increment loop index within loop body step by step in the Racket programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the bc programming language
You may also check:How to resolve the algorithm Loops/Foreach step by step in the SAS programming language
You may also check:How to resolve the algorithm Giuga numbers step by step in the Euler programming language
You may also check:How to resolve the algorithm Even or odd step by step in the Raku programming language