Latin Squares

June 18, 2019

We build a list of integers from 0 to n − 1 in order, shuffle the list, build the list into a matrix by rotating n − 1 times stacking the lists atop each other, shuffle the rows, transpose the matrix, and shuffle the rows again:

(define (latin n)
  (do ((n n (- n 1))
       (m (list (shuffle (range n))) (cons (rot 1 (car m)) m)))
      ((= n 1) (shuffle (apply map list (shuffle m))))))

The standard idiom for transposing a list of lists is apply map list. Here’s an example:

> (for-each (lambda (row) (display (map f2 row)) (newline)) (latin 25))
( 5 15 21  6  8  3  9  1 18 24 20 19 14  0  7  4 13 22  2 12 23 17 10 11 16)
(11 13  1  3  6  0 19 12 23 21  7 17 16 15  9  5  4  2 20  8 24 14 18 22 10)
( 9  2  0  5  4 11 18 15  8  3 16 23 21 22 10  7 20 17 14 13  6 24 12 19  1)
(21 18  7 14 17 16  0  9 22 20  6 15  4 10  3 24 23 12  8 19  2 13 11  1  5)
( 0  8 10 21 24  1 22 18 17 16  5  2  7 12 11  3  6 13  4 23 14 20 19 15  9)
(15  6 18  1 21 12  2 23 14 10 11 20  9  8 22  0  3  4  5 24 16  7 17 13 19)
(18 14 22  9  7 19  8  2  4 11  1  6  0 17 12 10 16 24 21 20  5  3 13 23 15)
(12 24 19 10 16 18 13 17 20  9  0  4 11 23 15  1 21  6  3 14  7  5  2  8 22)
(14  9  4  2 22 20 21  5  0 13 23  1  8  7 24 17 19 10 18 11 15 12  3 16  6)
( 4  0 24  8 12  6  7 21 10 23  2  9 17  3 20 13 15 11 22  1 18 19 16  5 14)
(23 16  2 19  9 17  6 20  5 22 12  3 15 14  8 18 10 21  1  7 11  0  4 24 13)
(13  3 23 12  1  8 20 24 16 18 22  7 19  6  2 15  0  5 11 21 10  9 14  4 17)
(24 10 20 17 19 14  3  7 11  2  8  0 13 16  6 23 18  1 12  9 22 15  5 21  4)
(17  7 13 22 11  2 24  4  3 15 18 21 12 20 23 19  9 16 10  5  0  1  6 14  8)
( 6  1 14 23 18 24  5 16  9 17 13 11  2 21  4  8 12  0 15 10 19 22  7  3 20)
(16 19  5 20  2  7  1 11 15  4 24 12  6  9 21 14 17 18 23 22 13  8  0 10  3)
( 1 23  9 16 14 10 15 19  2  7  3 13  5 18  0 21 24  8  6 17 20  4 22 12 11)
( 8 21 17 18 10 23  4 14  7 19 15  5 22 24 13 12  1  3  0 16  9 11 20  6  2)
(22  4 12  0  3 15 17  8 24  1  9 14 10 13 19 11  5 20  7  6 21 16 23  2 18)
(10 17 11  7 20  9 12 22 13  5 21  8  3 19  1 16 14 23 24  2  4  6 15 18  0)
( 3 12 16 24 23 21 11 10 19 14  4 22 20  1  5  6  8 15 13 18 17  2  9  0  7)
( 2  5  8 15  0 13 14  6 21 12 19 16 18  4 17 22 11  7  9  3  1 10 24 20 23)
( 7 22  3  4 13  5 10  0 12  6 14 18 24 11 16 20  2 19 17 15  8 23  1  9 21)
(19 20 15 11  5 22 23 13  6  0 10 24  1  2 18  9  7 14 16  4  3 21  8 17 12)
(20 11  6 13 15  4 16  3  1  8 17 10 23  5 14  2 22  9 19  0 12 18 21  7 24)

We write a cheesy little function f2 to format numbers as two-digit strings:

(define (f2 n)
  (let ((s (number->string n)))
    (if (< n 10) (string-append " " s) s)))

You can run the program at https://ideone.com/OldxFK.

Pages: 1 2

11 Responses to “Latin Squares”

  1. Zack said

    Interesting problem. Here is my take on it, using Julia 1.0:

    using Random

    function main(n::Int64)
    A = Array{Int64}(undef, n, n)
    x = Array{Int64}(undef, n)
    A[1,:] = randperm(n) .- 1

    for i = 2:n
        done = false
    
        while !done
            x = randperm(n) .- 1
            done = true
    
            for j = 1:n
                if x[j] in A[1:(i-1),j]; done = false; break; end
            end
        end
    
        A[i,:] = x
    end
    
    return A
    

    end

    Now, if we don’t really care about having each row of the LS as a random sequence of numbers and we just care about it being distinct from the previous rows, we can use a fairly simpler function:

    function main2(n::Int64)
    A = Array{Int64}(undef, n, n)
    A[1,:] = randperm(n) .- 1

    for i = 2:n
        for j = 1:n
            A[i,j] = mod(A[i-1,j] + 1, n)
        end
    end
    
    return A
    

    end

    Either way, we can obtain a latin square, A, which can be quite handy as an auxiliary tool for building games like Sudoku. Cheers

  2. Paul said

    In Python. I used Latin squares before in statistics for faster convergence in multidimensional random sampling.

    import random
    from pprint import pprint
    
    def create_latin(dim):
        frow = list(range(dim))
        random.shuffle(frow)
        labels = [frow]
        for _ in range(dim-1):
            frow = frow[1:] + [frow[0]]
            labels.append(frow)
        random.shuffle(labels)
        random.shuffle(list(zip(*labels)))
        return labels
    
    def assert_latin(arr2d):
        n = len(arr2d)
        sorted_nums = list(range(n))
        for row in arr2d:
            assert sorted(row) == sorted_nums
        for col in zip(*arr2d):
            assert sorted(col) == sorted_nums
    
    latin = create_latin(5)
    assert_latin(latin)
    pprint(latin)
    
  3. Zack said

    @Paul. That’s intriguing. Could you please elaborate on this? Are you optimizing for a particular metric / heuristic in this kind of sampling? If so, what? I’m asking because I’ve played around with multi-dimensional sampling too over the years. Cheers

  4. Paul said

    @Zack. I will dig in my old files and see if I have a nice example. In the meantime you can read the Wikipedia page on “Latin hypercube sampling”.

  5. Paul said

    @Zack. I put an example on ideone. To run it you should have numpy, scipy, pyDOE and matplotlib installed.

  6. Zack said

    @Paul. Many thanks!

  7. Alex B. said

    @paul. I think you may have a bug in the randomisation. If I understand correctly you’re doing a transpose and randomise on the shuffled list, so that each row (although appearing in random order) is not a simple rotation of the first row.
    In that case, you need to do something like:

    labels = list(zip(*labels))
    random.shuffle(labels)
    

    Otherwise random.shuffle is shuffling an unreferenced list (returned by the list() call), and not labels, which you’re then returning.

    (My apologies if I’ve misunderstood)

  8. Paul said

    @Alex B: I understand your concerns. I had them too. However, after checking if the result is a latin square I thought I did it right. But you are right the last shuffle doesn’t work and your suggestion works fine. Thanks.

  9. Daniel said

    Here’s a numpy-based solution in Python.

    import numpy as np
    
    def latin_square(n):
        arange = np.arange(n)
        x = np.stack(tuple(np.roll(arange, x) for x in range(n)))
        x[:, arange] = x[:, np.random.permutation(arange)]
        x[arange, :] = x[np.random.permutation(arange), :]
        return x
    
    print(latin_square(5))
    

    Output:

    array([[3, 1, 0, 2, 4],
           [1, 4, 3, 0, 2],
           [0, 3, 2, 4, 1],
           [4, 2, 1, 3, 0],
           [2, 0, 4, 1, 3]])
    
  10. Daniel said

    Line 5 in my preceding solution can be simplified by removing the call to “tuple”.

    x = np.stack(np.roll(arange, x) for x in range(n))
    
  11. Stephane said

    All the solutions presented here are valid but are not truly “random”. Just swapping rows and columns keeps some symmetry: for example, from the big Latin Square at the top of the page, pick up two consecutive numbers from the first rows, for example, 23 and 21 of the second row. Just below these numbers are 8 and 3. Now, on any row, find 23 and 21 (which most probably won’t be consecutive) and from each number, in its column, find 8 (for 23) and 3 (for 21), you will see that they are on the same row! So, is it possible to build a Latin Square without this property and how would you do it?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: