{{draft task}}

A Latin square of size n is an arrangement of n symbols in an n-by-n square in such a way that each row and column has each symbol appearing exactly once.

A randomised Latin square generates random configurations of the symbols for any given n.

;Example n=4 randomised Latin square:

0 2 3 1
2 1 0 3
3 0 1 2
1 3 2 0

;Task:

Create a function/routine/procedure/method/... that given n generates a randomised Latin square of size n.

Use the function to generate ''and show here'', two randomly generated squares of size 5.

;Note: Strict ''Uniformity'' in the random generation is a hard problem and '''not''' a requirement of the task.

;Reference:

• [[wp:Latin_square|Latin square]]
• [http://oeis.org/A002860 OEIS A002860]

=={{header|F_Sharp|F#}}== This solution uses functions from [[Factorial_base_numbers_indexing_permutations_of_a_collection#F.23]] and [[Latin_Squares_in_reduced_form#F.23]]. This solution generates completely random uniformly distributed Latin Squares from all possible Latin Squares of order 5. It takes 5 thousandths of a second can that really be called hard?

// Generate 2 Random Latin Squares of order 5. Nigel Galloway: July 136th., 2019
let N=let N=System.Random() in (fun n->N.Next(n))
let rc()=let β=lN2p [|0;N 4;N 3;N 2|] [|0..4|] in Seq.item (N 56) (normLS 5) |> List.map(lN2p [|N 5;N 4;N 3;N 2|]) |> List.permute(fun n->β.[n]) |> List.iter(printfn "%A")
rc(); printfn ""; rc()

{{out}}

[|5; 3; 1; 4; 2|]
[|1; 4; 5; 2; 3|]
[|4; 1; 2; 3; 5|]
[|2; 5; 3; 1; 4|]
[|3; 2; 4; 5; 1|]

[|4; 1; 2; 5; 3|]
[|3; 5; 1; 2; 4|]
[|2; 4; 5; 3; 1|]
[|1; 2; 3; 4; 5|]
[|5; 3; 4; 1; 2|]

I thought some statistics might be interesting so I generated 1 million Latin Squares of order 5. There are 161280 possible Latin Squares of which 3174 were not generated. The remainder were generated:

Times Generated    Number of Latin Squares
     1                       1776
     2                       5669
     3                      11985
     4                      19128
     5                      24005
     6                      25333
     7                      22471
     8                      18267
     9                      12569
    10                       7924
    11                       4551
    12                       2452
    13                       1130
    14                        483
    15                        219
    16                         93
    17                         37
    18                          5
    19                          7
    20                          2

Factor

A brute force method for generating uniformly random Latin squares. Repeatedly select a random permutation of (0, 1,...n-1) and add it as the next row of the square. If at any point the rules for being a Latin square are violated, start the entire process over again from the beginning.

USING: arrays combinators.extras fry io kernel math.matrices
prettyprint random sequences sets ;
IN: rosetta-code.random-latin-squares

: rand-permutation ( n -- seq ) <iota> >array randomize ;
: ls? ( n -- ? ) [ all-unique? ] column-map t [ and ] reduce ;
: (ls) ( n -- m ) dup '[ _ rand-permutation ] replicate ;
: ls ( n -- m ) dup (ls) dup ls? [ nip ] [ drop ls ] if ;
: random-latin-squares ( -- ) [ 5 ls simple-table. nl ] twice ;

MAIN: random-latin-squares

{{out}}

0 4 3 2 1
3 0 2 1 4
4 2 1 3 0
2 1 4 0 3
1 3 0 4 2

4 0 1 3 2
0 2 4 1 3
1 3 0 2 4
2 4 3 0 1
3 1 2 4 0

Go

Restarting Row method

As the task is not asking for large squares to be generated and even n = 10 is virtually instant, we use a simple brute force approach here known as the 'Restarting Row' method (see Talk page). However, whilst easy to understand, this method does not produce uniformly random squares.

package main

import (
    "fmt"
    "math/rand"
    "time"
)

type matrix [][]int

func shuffle(row []int, n int) {
    rand.Shuffle(n, func(i, j int) {
        row[i], row[j] = row[j], row[i]
    })
}

func latinSquare(n int) {
    if n <= 0 {
        fmt.Println("[]\n")
        return
    }
    latin := make(matrix, n)
    for i := 0; i < n; i++ {
        latin[i] = make([]int, n)
        if i == n-1 {
            break
        }
        for j := 0; j < n; j++ {
            latin[i][j] = j
        }
    }
    // first row
    shuffle(latin[0], n)

    // middle row(s)
    for i := 1; i < n-1; i++ {
        shuffled := false
    shuffling:
        for !shuffled {
            shuffle(latin[i], n)
            for k := 0; k < i; k++ {
                for j := 0; j < n; j++ {
                    if latin[k][j] == latin[i][j] {
                        continue shuffling
                    }
                }
            }
            shuffled = true
        }
    }

    // last row
    for j := 0; j < n; j++ {
        used := make([]bool, n)
        for i := 0; i < n-1; i++ {
            used[latin[i][j]] = true
        }
        for k := 0; k < n; k++ {
            if !used[k] {
                latin[n-1][j] = k
                break
            }
        }
    }
    printSquare(latin, n)
}

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

func main() {
    rand.Seed(time.Now().UnixNano())
    latinSquare(5)
    latinSquare(5)
    latinSquare(10) // for good measure
}

{{out}} Sample run:

[3 2 1 0 4]
[0 3 2 4 1]
[4 1 0 3 2]
[2 4 3 1 0]
[1 0 4 2 3]

[3 1 0 4 2]
[1 0 2 3 4]
[2 4 3 0 1]
[4 3 1 2 0]
[0 2 4 1 3]

[9 2 8 4 6 1 7 5 0 3]
[4 3 7 6 0 8 5 9 2 1]
[2 1 9 7 3 4 6 0 5 8]
[8 6 0 5 7 2 3 1 9 4]
[5 0 6 8 1 3 9 2 4 7]
[7 5 4 9 2 0 1 3 8 6]
[3 9 2 1 5 6 8 4 7 0]
[1 4 5 2 8 7 0 6 3 9]
[6 8 3 0 4 9 2 7 1 5]
[0 7 1 3 9 5 4 8 6 2]

Latin Squares in Reduced Form method

Unlike the "Restarting Row" method, this method does produce uniformly random Latin squares for n <= 6 (see Talk page) but is more involved and therefore slower. It reuses some (suitably adjusted) code from the [https://rosettacode.org/wiki/Latin_Squares_in_reduced_form#Go Latin Squares in Reduced Form] and [https://rosettacode.org/wiki/Permutations#non-recursive.2C_lexicographical_order Permutations] tasks.

package main

import (
    "fmt"
    "math/rand"
    "sort"
    "time"
)

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 reducedLatinSquares(n int) []matrix {
    var rls []matrix
    if n < 0 {
        n = 0
    }
    rlatin := make(matrix, n)
    for i := 0; i < n; i++ {
        rlatin[i] = make([]int, n)
    }
    if n <= 1 {
        return append(rls, rlatin)
    }
    // first row
    for j := 0; j < n; j++ {
        rlatin[0][j] = j + 1
    }
    // recursive closure to compute reduced latin squares
    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 {
                rl := copyMatrix(rlatin)
                rls = append(rls, rl)
            }
        }
        return
    }

    // remaining rows
    recurse(2)
    return rls
}

func copyMatrix(m matrix) matrix {
    le := len(m)
    cpy := make(matrix, le)
    for i := 0; i < le; i++ {
        cpy[i] = make([]int, le)
        copy(cpy[i], m[i])
    }
    return cpy
}

func printSquare(latin matrix, n int) {
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            fmt.Printf("%d ", latin[i][j]-1)
        }
        fmt.Println()
    }
    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
}

// generate permutations of first n numbers, starting from 0.
func pList(n int) matrix {
    fact := factorial(uint64(n))
    perms := make(matrix, fact)
    a := make([]int, n)
    for i := 0; i < n; i++ {
        a[i] = i
    }
    t := make([]int, n)
    copy(t, a)
    perms[0] = t
    n--
    var i, j int
    for c := uint64(1); c < fact; c++ {
        i = n - 1
        j = n
        for a[i] > a[i+1] {
            i--
        }
        for a[j] < a[i] {
            j--
        }
        a[i], a[j] = a[j], a[i]
        j = n
        i++
        for i < j {
            a[i], a[j] = a[j], a[i]
            i++
            j--
        }
        t := make([]int, n+1)
        copy(t, a)
        perms[c] = t
    }
    return perms
}

func generateLatinSquares(n, tests, echo int) {   
    rls := reducedLatinSquares(n)
    perms := pList(n)
    perms2 := pList(n - 1)
    for test := 0; test < tests; test++ {
        rn := rand.Intn(len(rls))
        rl := rls[rn] // select reduced random square at random
        rn = rand.Intn(len(perms))
        rp := perms[rn] // select a random permuation of 'rl's columns
        // permute columns
        t := make(matrix, n)
        for i := 0; i < n; i++ {
            t[i] = make([]int, n)
        }
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                t[i][j] = rl[i][rp[j]]
            }
        }
        rn = rand.Intn(len(perms2))
        rp = perms2[rn] // select a random permutation of 't's rows 2 to n
        // permute rows 2 to n
        u := make(matrix, n)
        for i := 0; i < n; i++ {
            u[i] = make([]int, n)
        }
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if i == 0 {
                    u[i][j] = t[i][j]
                } else {
                    u[i][j] = t[rp[i-1]+1][j]
                }
            }
        }
        if test < echo {
            printSquare(u, n)
        }
        if n == 4 {
            for i := 0; i < 4; i++ {
                for j := 0; j < 4; j++ {
                    u[i][j]--
                }
            }
            for i := 0; i < 4; i++ {
                copy(a[4*i:], u[i])
            }
            for i := 0; i < 4; i++ {
                if testSquares[i] == a {
                    counts[i]++
                    break
                }
            }
        }
    }
}

var testSquares = [4][16]int{
    {0, 1, 2, 3, 1, 0, 3, 2, 2, 3, 0, 1, 3, 2, 1, 0},
    {0, 1, 2, 3, 1, 0, 3, 2, 2, 3, 1, 0, 3, 2, 0, 1},
    {0, 1, 2, 3, 1, 2, 3, 0, 2, 3, 0, 1, 3, 0, 1, 2},
    {0, 1, 2, 3, 1, 3, 0, 2, 2, 0, 3, 1, 3, 2, 1, 0},
}

var (
    counts [4]int
    a      [16]int
)

func main() {
    rand.Seed(time.Now().UnixNano())
    fmt.Println("Two randomly generated latin squares of order 5 are:\n")
    generateLatinSquares(5, 2, 2)

    fmt.Println("Out of 1,000,000 randomly generated latin squares of order 4, ")
    fmt.Println("of which there are 576 instances ( => expected 1736 per instance),")
    fmt.Println("the following squares occurred the number of times shown:\n")
    generateLatinSquares(4, 1e6, 0)
    for i := 0; i < 4; i++ {
        fmt.Println(testSquares[i][:], ":", counts[i])
    }

    fmt.Println("\nA randomly generated latin square of order 6 is:\n")
    generateLatinSquares(6, 1, 1)
}

{{out}} Sample run:

Two randomly generated latin squares of order 5 are:

2 1 3 4 0 
4 3 0 1 2 
1 0 2 3 4 
0 4 1 2 3 
3 2 4 0 1 

1 2 3 4 0 
0 3 4 2 1 
2 4 0 1 3 
4 0 1 3 2 
3 1 2 0 4 

Out of 1,000,000 randomly generated latin squares of order 4, 
of which there are 576 instances ( => expected 1736 per instance),
the following squares occurred the number of times shown:

[0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0] : 1737
[0 1 2 3 1 0 3 2 2 3 1 0 3 2 0 1] : 1736
[0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2] : 1726
[0 1 2 3 1 3 0 2 2 0 3 1 3 2 1 0] : 1799

A randomly generated latin square of order 6 is:

3 5 1 0 4 2 
2 0 5 4 1 3 
0 4 2 5 3 1 
1 3 4 2 0 5 
5 1 0 3 2 4 
4 2 3 1 5 0 

Javascript

class Latin {
  constructor(size = 3) {
    this.size = size;
    this.mst = [...Array(this.size)].map((v, i) => i + 1);
    this.square = Array(this.size).fill(0).map(() => Array(this.size).fill(0));

    if (this.create(0, 0)) {
      console.table(this.square);
    }
  }

  create(c, r) {
    const d = [...this.mst];
    let s;
    while (true) {
      do {
        s = d.splice(Math.floor(Math.random() * d.length), 1)[0];
        if (!s) return false;
      } while (this.check(s, c, r));

      this.square[c][r] = s;
      if (++c >= this.size) {
        c = 0;
        if (++r >= this.size) {
          return true;
        }
      }
      if (this.create(c, r)) return true;
      if (--c < 0) {
        c = this.size - 1;
        if (--r < 0) {
          return false;
        }
      }
    }
  }

  check(d, c, r) {
    for (let a = 0; a < this.size; a++) {
      if (c - a > -1) {
        if (this.square[c - a][r] === d)
          return true;
      }
      if (r - a > -1) {
        if (this.square[c][r - a] === d)
          return true;
      }
    }
    return false;
  }
}
new Latin(5);

{{out}}

3 5 4 1 2
4 3 1 2 5
1 2 3 5 4
5 1 2 4 3
2 4 5 3 1
 
4 5 1 3 2
3 1 4 2 5
5 4 2 1 3
1 2 3 5 4
2 3 5 4 1

Julia

Using the Python algorithm as described in the discussion section.

using Random

shufflerows(mat) = mat[shuffle(1:end), :]
shufflecols(mat) = mat[:, shuffle(1:end)]

function addatdiagonal(mat)
    n = size(mat)[1] + 1
    newmat = similar(mat, size(mat) .+ 1)
    for j in 1:n, i in 1:n
        newmat[i, j] = (i == n && j < n) ? mat[1, j] : (i == j) ? n - 1 :
            (i < j) ? mat[i, j - 1] : mat[i, j]
    end
    newmat
end

function makelatinsquare(N)
    mat = [0 1; 1 0]
    for i in 3:N
        mat = addatdiagonal(mat)
    end
    shufflecols(shufflerows(mat))
end

function printlatinsquare(N)
    mat = makelatinsquare(N)
    for i in 1:N, j in 1:N
        print(rpad(mat[i, j], 3), j == N ? "\n" : "")
    end
end

printlatinsquare(5), println("\n"), printlatinsquare(5)

{{out}}

1  3  0  4  2
3  0  4  2  1
0  4  2  1  3
2  1  3  0  4
4  2  1  3  0


2  0  1  3  4
4  3  2  1  0
3  2  0  4  1
1  4  3  0  2
0  1  4  2  3

M2000 Interpreter

Easy Way

One row shuffled to be used as the destination row. One more shuffled and then n times rotated by one and stored to array

for 40x40 need 2~3 sec, including displaying to screen

We use the stack of values, a linked list, for pushing to top (Push) or to bottom (Data), and we can pop from top using Number or by using Read A to read A from stack. Also we can shift from a chosen position to top using Shift, or using shiftback to move an item from top to chosen position. So we shuffle items by shifting them.

Module FastLatinSquare {
	n=5
	For k=1 To 2
		latin()
	Next
	n=40
	latin()
	Sub latin()
		Local i,a, a(1 To n), b, k
		Profiler
		flush
		Print "latin square ";n;" by ";n
		For i=1 To n
			Push i
		Next i
		For i=1 To n div 2
			Shiftback random(2, n)
		Next i
		a=[]
		Push ! stack(a)
		a=array(a)  ' change a from stack to array
		For i=1 To n*10
			Shiftback random(2, n)
		Next i
		For i=0 To n-1
			Data number  ' rotate by one the stack items
			b=[]    ' move stack To b, leave empty stack
			a(a#val(i))=b
			Push ! stack(b)  ' Push from a copy of b all items To stack
		Next i
		flush
		For k=1 To  n div 2
			z=random(2, n)
			For i=1 To n
				a=a(i)
				stack a {
					shift z
				}
			Next
		Next
		For i=1 To n
			a=a(i)
			a(i)=array(a)  ' change To array from stack
		Next i
		For i=1 To n
			Print a(i)
		Next i
		Print TimeCount
	End Sub
}
FastLatinSquare

Hard Way

for 5x5 need some miliseconds

for 16X16 need 56 seconds

for 20X20 need 22 min (as for 9.8 version)

Module LatinSquare (n, z=1, f$="latin.dat", NewFile As Boolean=False) {
	If Not Exist(f$)  Or NewFile Then
		Open f$ For Wide Output As f
	Else
		Open f$ For Wide Append As f
	End If
	ArrayToString=Lambda -> {
		Shift 2  ' swap two top values in stack
		Push Letter$+Str$(Number)
	}
	Dim line(1 to n)
	flush   ' erase current stack of value
	z=if(z<1->1, z)
	newColumn()
	For j=1 To z
		Profiler
		ResetColumns()
		For i=1 To n
			placeColumn()
		Next
		Print "A latin square of ";n;" by ";n
		For i=1 To n
			Print line(i)
			Print #f, line(i)#Fold$(ArrayToString)
		Next 
		Print TimeCount
		Refresh
	Next 
	close #f
	Flush  ' empty stack again
	End
	Sub ResetColumns()
		Local i
		For i=1 To n:line(i)=(,):Next
	End Sub
	Sub newColumn()
		Local i
		For i=1 To n : Push i: Next
	End Sub
	Sub shuffle()
		Local i
		For i=1 To n div 2: Shift Random(2, n): Next
	End Sub
	Sub shuffleLocal(x)
		If Stack.size<=x Then Exit Sub
		Shift Random(x+1, Stack.size)
		Shiftback x
	End Sub
	Sub PlaceColumn()
		Local i, a, b, k
		shuffle()
		Do
			data number   ' rotate one position
			k=0
			For i=1 To n
				a=line(i)  ' get the pointer
				Do
				If a#Pos(Stackitem(i))=-1 Then k=0 :Exit Do
				shuffleLocal(i)
				k++
				Until k>Stack.size-i
				If k>0 Then Exit For
			Next
		Until k=0
		For i=1 To n
			a=line(i) 
			Append a, (Stackitem(i),)
		Next
	End Sub
}
Form 100,50
LatinSquare 5, 2, True
LatinSquare 16

{{out}}

A latin square of 5 by 5
 4 5 3 1 2
 5 4 2 3 1
 2 1 5 4 3
 1 3 4 2 5
 3 2 1 5 4
A latin square of 5 by 5
 4 3 5 1 2
 2 4 3 5 1
 1 2 4 3 5
 5 1 2 4 3
 3 5 1 2 4
A latin square of 16 by 16
12 14 5 16 1 2 7 15 9 11 10 8 13 3 6 4
 3 13 16 12 7 4 1 11 5 6 15 2 8 14 10 9
 13 2 8 3 4 12 5 9 14 7 16 10 6 1 15 11
 8 3 13 9 2 10 16 1 15 14 5 4 11 7 12 6
 4 12 2 7 5 3 6 10 1 9 11 16 14 8 13 15
 16 8 3 4 14 6 13 7 11 10 9 15 1 12 2 5
 15 4 14 1 16 8 2 13 6 12 7 9 10 11 5 3
 11 16 12 10 15 9 4 5 7 1 8 6 3 13 14 2
 10 15 4 5 12 16 3 6 8 13 1 11 7 2 9 14
 9 11 15 8 3 1 14 12 13 4 6 5 2 16 7 10
 7 10 11 13 9 14 15 4 3 5 2 12 16 6 1 8
 6 7 10 2 8 13 9 16 12 15 14 3 5 4 11 1
 5 6 1 14 13 11 8 2 10 3 12 7 15 9 4 16
 2 5 6 15 11 7 12 14 4 8 3 1 9 10 16 13
 1 9 7 11 6 15 10 8 2 16 13 14 4 5 3 12
 14 1 9 6 10 5 11 3 16 2 4 13 12 15 8 7