2
\$\begingroup\$

I created an algorithm for generating Latin Square. The algorithm uses the first n permutations (Not n!) orderings of a distinct row of numbers. This is then assigned to a 2d list.

import itertools

def latin_square(rows, numbers):
    assert rows is not None, "row is required to not be None"
    assert rows >= 0, "row is required to be zero or more, including zero"
    assert numbers is not None, "numbers is required to not be None"
    
    square = [[numbers[0] for row in range(rows)] for col in range(rows)]
    line = [] 
    for row, line in enumerate(itertools.permutations(numbers, rows)):
        if row == rows:
            break
        for col in range(len(line)):
            square[row][col] = line[col]
    return square 

def test_latin_square():
    assert latin_square(1, [1]) == [[1]]
    assert latin_square(2, [0, 1]) == [[0, 1], [1, 0]]
    assert latin_square(2, [-1, -2]) == [[-1, -2], [-2, -1]]
    assert latin_square(3, [3, 2, 1]) == [[3, 2, 1], [3, 1, 2], [2, 3, 1]]

test_latin_square() 


\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Functionality

Your code is incorrect, as you can see in your fourth test case:

latin_square(3, [3, 2, 1]) == [[3, 2, 1],
                               [3, 1, 2],
                               [2, 3, 1]]

This is not a latin square, since there are two 3s in the first column and two 1s in the third column. This seems like you wrote the code first and then copied its output to the test cases. It should obviously be the other way round.

The most straight-forward approach would probably be simply rotating the list of numbers by one in either direction to get each next row. You should of course make sure to only use distinct numbers from the provided input list numbers.


Other suggestions

These suggestions will improve the existing implementation, but will not fix the incorrect functionality.


assert statements should only be used for testing, as they will be ignored in optimized mode. More about optimized mode here. Rather you should check these conditions with an if-statement and raise meaningful errors (instead of AssertionErrors). ValueError or TypeError should be the most fitting here (but you could implement your own custom exceptions). One example:

if len(set(numbers)) < rows:
    raise ValueError(f"Number of distinct numbers must be greater than or equal to {rows=}")

You also don't need to explicitly check for rows is None and numbers is None, as None values will lead to a TypeError anyway. Manually checking and providing a meaningful message to the user usually doesn't hurt though.


square = [[numbers[0] for _ in range(rows)] for _ in range(rows)]

It's a well-known convention to name variables you don't use _. That immediately makes it clear to the reader that it's not used and removes unnecessary information.


You're doing too much manual work:

  1. You don't need to fill square with values only to replace them later
  2. You don't need to initialize line at all
  3. You shouldn't (most likely ever) do this:
for col in range(len(line)):
    square[row][col] = line[col]

All this snippet does is set the value of square[row] to list(line):

square = []

for row, line in enumerate(itertools.permutations(numbers, rows)):
    if row == rows:
        break

    square.append(list(line))
\$\endgroup\$
2
  • \$\begingroup\$ Could I replace the code with just sifting without generating permutations? \$\endgroup\$ Commented Jun 4, 2021 at 17:45
  • \$\begingroup\$ I presume you mean shifting. Shifting will of course produce certain permutations, but you don't need itertools.permutations for it. Simply take rows number of distinct numbers for the first row, then keep shifting them (left or right) by one to get the subsequent row. You're very welcome to come back here for further feedback once you've implemented that. \$\endgroup\$ Commented Jun 4, 2021 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.