How to resolve the algorithm Latin Squares in reduced form step by step in the Go programming language

Published on 12 May 2024 09:40 PM
#Go

How to resolve the algorithm Latin Squares in reduced form step by step in the Go 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 Go programming language

This Go code generates reduced Latin squares of a given order and calculates their count. Here's a detailed explanation:

  1. Matrix Type: The code defines a type matrix as a 2D slice of integers to represent Latin squares.

  2. Derangements: The dList function generates derangements of the first n numbers, starting with start in the first place. A derangement is a permutation where no element appears in its original position.

  3. Reduced Latin Square: The reducedLatinSquare function generates reduced Latin squares of order n. It initializes a matrix rlatin of size n x n, where the first row contains the numbers 1 to n.

  4. Recursive Closure: The recurse function is a recursive closure used to generate reduced Latin squares. It selects rows and columns to place the deranged numbers and checks if the resulting square is deranged and valid. If a valid square is found, it is printed and added to the count.

  5. Printing Latin Squares: The printSquare function prints a given Latin square in a readable format.

  6. Factorial Calculation: The factorial function calculates the factorial of a given positive integer n.

  7. Main Function: The main function demonstrates the code by generating and printing reduced Latin squares of order 4, as well as calculating and displaying the count and total number of Latin squares for orders 1 to 6.

This code generates reduced Latin squares, which are Latin squares where the first row is deranged. A Latin square is a square matrix where each row and column contains each number from 1 to the order of the square exactly once. The reduced Latin square condition requires an additional constraint that the first row must be a derangement.

The code uses a recursive algorithm to generate derangements and build reduced Latin squares. It also counts the total number of Latin squares by multiplying the count of reduced Latin squares with various factorial terms. The output includes specific reduced Latin squares of order 4 and the count and total number of Latin squares for orders 1 to 6.

Source code in the go programming language

package main

import (
    "fmt"
    "sort"
)

type matrix [][]int

// generate derangements of first n numbers, with 'start' in first place.
func dList(n, start int) (r matrix) {
    start-- // use 0 basing
    a := make([]int, n)
    for i := range a {
        a[i] = i
    }
    a[0], a[start] = start, a[0]
    sort.Ints(a[1:])
    first := a[1]
    // recursive closure permutes a[1:]
    var recurse func(last int)
    recurse = func(last int) {
        if last == first {
            // bottom of recursion.  you get here once for each permutation.
            // test if permutation is deranged.
            for j, v := range a[1:] { // j starts from 0, not 1
                if j+1 == v {
                    return // no, ignore it
                }
            }
            // yes, save a copy
            b := make([]int, n)
            copy(b, a)
            for i := range b {
                b[i]++ // change back to 1 basing
            }
            r = append(r, b)
            return
        }
        for i := last; i >= 1; i-- {
            a[i], a[last] = a[last], a[i]
            recurse(last - 1)
            a[i], a[last] = a[last], a[i]
        }
    }
    recurse(n - 1)
    return
}

func reducedLatinSquare(n int, echo bool) uint64 {
    if n <= 0 {
        if echo {
            fmt.Println("[]\n")
        }
        return 0
    } else if n == 1 {
        if echo {
            fmt.Println("[1]\n")
        }
        return 1
    }
    rlatin := make(matrix, n)
    for i := 0; i < n; i++ {
        rlatin[i] = make([]int, n)
    }
    // first row
    for j := 0; j < n; j++ {
        rlatin[0][j] = j + 1
    }

    count := uint64(0)
    // recursive closure to compute reduced latin squares and count or print them
    var recurse func(i int)
    recurse = func(i int) {
        rows := dList(n, i) // get derangements of first n numbers, with 'i' first.
    outer:
        for r := 0; r < len(rows); r++ {
            copy(rlatin[i-1], rows[r])
            for k := 0; k < i-1; k++ {
                for j := 1; j < n; j++ {
                    if rlatin[k][j] == rlatin[i-1][j] {
                        if r < len(rows)-1 {
                            continue outer
                        } else if i > 2 {
                            return
                        }
                    }
                }
            }
            if i < n {
                recurse(i + 1)
            } else {
                count++
                if echo {
                    printSquare(rlatin, n)
                }
            }
        }
        return
    }

    // remaining rows
    recurse(2)
    return count
}

func printSquare(latin matrix, n int) {
    for i := 0; i < n; i++ {
        fmt.Println(latin[i])
    }
    fmt.Println()
}

func factorial(n uint64) uint64 {
    if n == 0 {
        return 1
    }
    prod := uint64(1)
    for i := uint64(2); i <= n; i++ {
        prod *= i
    }
    return prod
}

func main() {
    fmt.Println("The four reduced latin squares of order 4 are:\n")
    reducedLatinSquare(4, true)

    fmt.Println("The size of the set of reduced latin squares for the following orders")
    fmt.Println("and hence the total number of latin squares of these orders are:\n")
    for n := uint64(1); n <= 6; n++ {
        size := reducedLatinSquare(int(n), false)
        f := factorial(n - 1)
        f *= f * n * size
        fmt.Printf("Order %d: Size %-4d x %d! x %d! => Total %d\n", n, size, n, n-1, f)
    }
}

You may also check:How to resolve the algorithm Bitmap/Write a PPM file step by step in the Phix programming language
You may also check:How to resolve the algorithm Middle three digits step by step in the Nim programming language
You may also check:How to resolve the algorithm Inheritance/Single step by step in the Oberon-2 programming language
You may also check:How to resolve the algorithm Sort a list of object identifiers step by step in the jq programming language
You may also check:How to resolve the algorithm Flow-control structures step by step in the Nemerle programming language