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.

Advertisements

Pages: 1 2

10 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))
    

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: